프로그래머스 : 숨바꼭질(Java)

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

---

 

 

[풀이]

 

 BFS를 구현하여서 풀었는데 처음에 이 문제를 풀지 못했다. 그래서 다른 분들이 푼 코드를 보고 푸는 방식을 공부한 후에 풀었다. for문에서 x-1 , x+1, x * 2를 가는 방식을 BFS에 구현하는 것이 하나의 주의할 부분, 두번째는 N과 K가 같을때의 조건을 추가하는 것이 또 하나의 주의할 부분이라고 생각한다. 이 문제에 대해서 100퍼센트 이해하지는 못한 느낌이 들어 주말에 다시 한번 풀어봐야할 것 같다.

 

---

[코드]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    static int[] visited;
    static int N, K;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String input_line = bufferedReader.readLine();
        StringTokenizer st = new StringTokenizer(input_line, " ");

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        visited = new int[100001];

        if (N == K) {
            System.out.println(0);
        } else {
            bfs(N, K);
        }
    }

    public static void bfs(int n, int k) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        visited[n] = 1;

        while (!queue.isEmpty()) {
            int now = queue.poll();

            for (int i = 0; i < 3; i++) {
                int next;

                if (i == 0) {
                    next = now + 1;
                } else if (i == 1) {
                    next = now - 1;
                } else {
                    next = now * 2;
                }

                if (next == k) {
                    System.out.println(visited[now]);
                    return;
                }

                if (next >= 0 && next < visited.length && visited[next] == 0) {
                    queue.offer(next);
                    visited[next] = visited[now] + 1;
                }
            }
        }
    }
}