다익스트라 (백준 13549 숨바꼭질 3)

다익스트라로 풀 수 있는 문제상황

• 한 지점에서 다른 한 지점까지의 최단 경로
• 한 지점에서 다른 모든 지점까지의 최단 경로
• 모든 지점에서 다른 모든 지점까지의 최단 경로

 

해당 문제는 한 지점에서 다른 한 지점까지의 최단 경로를 구해야 하는 문제이다.

 

문제를 그래프로 바꾸는게 중요하다고 생각한다.

 

수빈이는 위치 X에서 -1, +1, *2 로 움직일 수 있으니까

 

위치 X를 노드라고 생각했을 때 X-1, X+1, X*2 를 연결된 노드, 가중치는 문제에서 주어진 (1, 1, 0) 으로 생각했다.

 

다익스트라 알고리즘 (우선순위큐 활용) 코드

package com.mincheolsong;
import java.io.*;
import java.util.*;

public class Main {

    // boj 13549 숨바꼭질
    static final int INF = (int)1e9;
    static int N,K;
    static int[] dist;

    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());

        if(N>=K){
            System.out.println(N-K);
            return;
        }

        dist = new int[100001];
        Arrays.fill(dist,INF);

        PriorityQueue<Point> pq = new PriorityQueue<>();
        pq.offer(new Point(N,0));
        dist[N]=0;

        while(!pq.isEmpty()){
            Point current = pq.poll();

            if(current.x == K){
                System.out.println(current.w); // 정답 출력
                break;
            }

            if(dist[current.x] < current.w) continue; // 방문체크

            // -1 위치로 이동하는 경우 (1초 걸림)
            if(current.x - 1 >= 0 && current.w + 1 < dist[current.x - 1]){
                dist[current.x - 1] = current.w + 1;
                pq.offer(new Point(current.x - 1,current.w + 1));
            }

            // +1 위치로 이동하는 경우 (1초 걸림)
            if(current.x + 1 <= 100000 && current.w + 1 < dist[current.x + 1]){
                dist[current.x + 1] = current.w + 1;
                pq.offer(new Point(current.x + 1,current.w + 1));
            }

            // *2 위치로 이동하는 경우 (0초 걸림)
            if(current.x * 2 <= 100000 && current.w + 0 < dist[current.x * 2]){
                dist[current.x * 2] = current.w;
                pq.offer(new Point(current.x * 2, current.w));
            }
        }

    }

}

class Point implements Comparable<Point>{
    int x,w;

    public Point(int x,int w){
        this.x = x;
        this.w = w;
    }

    @Override
    public int compareTo(Point o){
        return this.w - o.w;
    }
}