백준 13549번 실패 (java)

접근

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

처음에는 bfs로 풀려고 도전했으나
bfs의 전제는 서로 뻗어가는 간선의 가중치가 모두 같다는 전제가 있다.

하지만 이 숨바꼭질 문제의 경우
최대한 시간을 적게 쓰는 방향으로 가야하기 때문에
순간이동하는 방법의 가중치가 다른 것들보다 더 높다.

또한 -1이 +1보다 가중치가 더 높은데
그 이유는 다른 예시를 찾아보려고 노력했으나 그 이유를 알지 못하겠다.

아마도 Q가 쌓여있을 때 그 안에 더 최소의 시간이 있으나 먼저 K에 도달한 값을 리턴하는 과정에서 문제가 생기는거 같다.

방법

따라서 다익스트라 방법을 사용하도록 한다.
다익스트라는 각 점에 도달하는 최소한의 거리를 구하는 문제에서 사용하는데 여기서 각 점은 1부터 100000까지이다.

각 점에 도달하는 최소의 비용을 넣기로 하는데 그 비용은 현재 값의 +1,0이며
각 점을 도달할 때는 현재 점의 +1, -1, *2로 진행된다.

정답이나 잘못된 접근의 풀이

import java.util.*;
import java.io.*;


public class Main{

    static boolean[] visit ;

    static int time;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        visit = new boolean[100_001];

        bfs(N,K);
        bw.write(Integer.toString(time));
        bw.flush();
        bw.close();
        br.close();



    }

    public static void bfs(int N , int K){
        Queue<int[]> Q = new LinkedList<>();
        Q.offer(new int[]{N,0});
        visit[N]=true;

        while(!Q.isEmpty()){
            int[] q = Q.poll();
            int x = q[0];

            if(x==K){
                time = q[1];
                break;
            }

            if( x*2<=100_000 && visit[x*2]==false){
                visit[x*2]=true;
                Q.offer(new int[]{x*2,q[1]});
                System.out.println("2*x:"+(2*x)+":"+ q[1]);
            }
            if(x-1>=0 && visit[x-1]==false){
                visit[x-1]=true;
                Q.offer(new int[]{x-1,q[1]+1});
                System.out.println("x-1:"+(x-1)+":"+ (q[1]+1));

            }
            if(x+1<=100_000 && visit[x+1]==false ){
                visit[x+1]=true;
                Q.offer(new int[]{x+1,q[1]+1});
                System.out.println("x+1:"+(x+1)+":"+ (q[1]+1));

            }
          


        }

    }

}

제대로 된 풀이

import java.util.*;
import java.io.*;


public class Main{

    static int[] dis ;
    static int INF = 987654321;

    static int time;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        dis = new int[100_001];
        Arrays.fill(dis,INF);

        dijk(N);

        bw.write(Integer.toString(dis[K]));
        bw.flush();
        bw.close();
        br.close();
    }

    public static void  dijk(int N){
        PriorityQueue<Cost> Q = new PriorityQueue<>((o1,o2)->{
            return o1.cost-o2.cost;
        });
        dis[N]=0;
        Q.offer(new Cost(N,0));
        while(!Q.isEmpty()){
            Cost q = Q.poll();
           // if(q.cost >dis[q.x]) continue;
            int x = q.x;
            if(x+1<=100_000&& dis[x+1]>1+q.cost){
                dis[x+1]=1+q.cost;
                Q.offer(new Cost(x+1,1+q.cost ));
            }
            if(x-1>=0 && dis[x-1]>1+q.cost){
                dis[x-1] = 1+q.cost;
                Q.offer(new Cost(x-1,1+q.cost ));
            }
            if(x*2<=100_000 && dis[x*2]>q.cost){
                dis[x*2] = q.cost;
                Q.offer(new Cost(x*2,q.cost ));
            }
        }
    }

    static class Cost{
        int x ;
        int cost;
        public Cost(int x, int cost){
            this.x =x;
            this.cost = cost;
        }
    }

}