백준 13549번 숨바꼭질 3 [ Java ]

13549번: 숨바꼭질 3

BFS로 풀었습니다.

가중치가 동일하지 않은 정점을 이동하기 때문에 Q에 넣는 순서가 2배수 -1 +1로 이동하지 않으면 틀리는 문제였습니다. 아직 이러한 유형을 완벽하게 이해하진 못해서 공부가 더 필요할 것 같습니다.

import java.util.*;

public class Main {
    public static void main(String[] args){
        Queue<Integer> Q = new LinkedList<>();
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        if (N>=K) {
            System.out.print(N-K);
            System.exit(0);
        }

        int[] dist = new int[100001];
        Arrays.fill(dist, -1);
        dist[N] = 0;
        Q.offer(N);
        while (!Q.isEmpty()){
            int cur = Q.poll();
            if (cur==K){
                System.out.println(dist[cur]);
                System.exit(0);
            }
            int idx = cur*2;
            while (idx <= 100000 && dist[idx]<0){
                dist[idx] = dist[cur];
                Q.offer(idx);
                idx*=2;
            }

            for (int n : new int[]{cur-1, cur+1}){
                if (n<0 || n>100000 || dist[n]>=0) continue;
                dist[n] = dist[cur]+1;
                Q.offer(n);
            }
        }
    }
}