[알고리즘][X] 숨바꼭질 3

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

13549번: 숨바꼭질 3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

    static boolean[] visited;
    static int N;
    static int K;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        visited = new boolean[100001];
        bfs(new int[] {N, 0});
        System.out.println(sb);
    }
//    (cur[0] !=0 && K % cur[0] == 0)
    private static void bfs(int[] start) {
        int[] dx = {-1, 1};
        Deque<int[]> deque = new ArrayDeque<>();
        deque.offer(start);
        visited[start[0]] = true;
        while (!deque.isEmpty()) {
            int[] cur = deque.poll();
            if (cur[0] == K ) {
                sb.append(cur[1]);
                return;
            }
            int next = cur[0];
            while (next != 0 && next * 2 <= 100000) {
                next *= 2;
                if (!visited[next]) {
                    deque.offer(new int[]{next, cur[1]});
                    visited[next] = true;
                }
            }
            for (int i = 0; i < 2; i++) {
                next = cur[0] + dx[i];
                if (0 <= next && next <= 100000 && !visited[next]) {
                    deque.offer(new int[] {next, cur[1] + 1});
                    visited[next] = true;
                }
            }

        }
    }
}

나의 풀이

- * 2만큼 해야 하는건데 * 1, 2, 3, 4...가 되게 만들었다. 문제를 잘못 이해한 것이다.

- while의 첫번째 if문에

K % cur[0] == 0

을 넣어놨는데 이렇게 되면 2의 제곱수의 곱이 아니다. 문제를 잘못 이해한 것이다. 주의 하자!!!!

- 그리고 while문과 for문의 순서를 바꾸면 안되는데 그 이유는 2를 곱한게 무조건 depth가 작기 때문에 queue에 먼저 들어가야 하기 때문이다. 그래야 return문에서 먼저 나올 수 있다.