[BOJ]1697번 - 숨바꼭질

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

1697번: 숨바꼭질

 

 

알고리즘 분류 : BFS, DFS, 백트래킹

 

public class Main {
    static Myscanner sc = new Myscanner();
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static int min = 100001;
    static boolean[] visited = new boolean[100001];

    public static void main(String[] args) {

        int N = sc.nextInt();
        int K = sc.nextInt();

        Queue<Integer> q = new LinkedList<>();
        q.offer(N);
        int depth = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int sz = 0; sz < size; sz++) {
                int here = q.poll();
                int[] switching = { here + 1, here - 1, here * 2 };

                if (here == K) {
                    out.println(depth);
                    out.close();
                    while (!q.isEmpty())
                        q.poll();
                    break;
                }

                if (visited[here])
                    continue;
                visited[here] = true;

                for (int idx = 0; idx < 3; idx++) {
                    if (switching[idx] >= 0 && switching[idx] < 100001) {
                        if (!visited[switching[idx]]) {
                            q.offer(switching[idx]);
                        }
                    }
                }
            }
            depth++;
        }
        out.close();
    }
}

 

BFS를 통한 최단거리를 찾는 문제로 해석하여 풀었다.

DFS로 풀려다 보니 런타임 에러/시간 초과가 나길래.. BFS로 전환해서 푸니 해결 완료..