[백준 13549] 숨바꼭질3 / 자바 / 다익스트라 알고리즘

#문제         

레벨: G5
알고리즘: BFS(그래프 탐색) 
풀이시간: 30분
힌트 참조 유무:

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

---

#문제 풀이        

직관적으로 가장 빠른 방법은 -초를 소비하고 2배를 가는 거다. 그렇다면 우린 다익스트라 알고리즘을 사용하면 된다. 최종 목표지까지 최소한의 비용을 알고싶다면 출발지부터 최소한의 비용의 노드들 부터 탐색하면 되는 거다. 그래서 미리 큐에 거듭해서 거리는 두배지만 시간은 그대로인 배열이 거듭해서 추가 되고 먼저 빼지는 거다.

---

#풀이 코드      

import java.util.*;

public class Main {
    static final int MAX = 100001;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 수빈이의 위치
        int K = sc.nextInt(); // 동생의 위치
        sc.close();

        int[] time = new int[MAX];
        Arrays.fill(time, -1);

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // 시간순서대로
        pq.offer(new int[]{N, 0});
        time[N] = 0;

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int pos = current[0];
            int t = current[1];

            if (pos == K) {
                System.out.println(t);
                return;
            }

            //pos*2 거리를 한 번도 탐색한 적 없거나 이 탐색이 더 짧은 경우만 탐색
            if (pos * 2 < MAX && (time[pos * 2] == -1 || t < time[pos * 2])) {
                pq.offer(new int[]{pos * 2, t});
                time[pos * 2] = t;
            }

            if (pos + 1 < MAX && (time[pos + 1] == -1 || t + 1 < time[pos + 1])) {
                pq.offer(new int[]{pos + 1, t + 1});
                time[pos + 1] = t + 1;
            }

            if (pos - 1 >= 0 && (time[pos - 1] == -1 || t + 1 < time[pos - 1])) {
                pq.offer(new int[]{pos - 1, t + 1});
                time[pos - 1] = t + 1;
            }
        }
    }
}