[백준 13549] 숨바꼭질 3(Java)

문제 링크 : https://www.acmicpc.net/problem/13549

이 문제는 다익스트라 알고리즘을 사용하여 풀 수 있습니다. 다익스트라 알고리즘 특성상 한 지점에서 모든 경로까지의 최솟값을 O((V + E) log V)의 시간 복잡도로 처리할 수 있습니다. 따라서 노드의 개수는 100001개, 간선의 개수는 노드 별 3가지이기 때문에 2초 내에 실행이 가능합니다.

다익스트라 알고리즘 적용 시 최솟값을 거리가 아닌 시간을 기준으로 잡습니다. 이후 순간이동 시 시간을 소비하지 않으므로 계산 시 가중치를 더하지 않으며 진행하고, 나머지 이동은 계산 시 가중치를 1씩 + 또는 - 하여 진행합니다.

여기서 주의할 점은 0의 시간을 가진다고 해서 이 값을 반복문으로 탐색하면 안된다는 점입니다. 그렇게 될 경우 걸어가는 경우 탐색하지 못하는 경우도 발생하기 때문에 3가지 케이스를 모두 독립적으로 실행하도록 해야 합니다.

다음은 코드입니다.

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

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

        int[] time = new int[100001];
        Arrays.fill(time,Integer.MAX_VALUE);
        time[N] = 0;

        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(N,0));

        boolean[] check = new boolean[100001];
        while(!queue.isEmpty()){
            Node start = queue.poll();
            if(check[start.node]) continue;
            check[start.node] = true;

            int next = start.node * 2;
            if (next <= 100000 && time[next] > time[start.node]) {
                time[next] = time[start.node];
                queue.add(new Node(next, time[next]));
            }

            int front = start.node - 1;
            if(front>=0 && time[front] > time[start.node]+1){
                time[front] = time[start.node]+1;
                queue.add(new Node(front,time[front]));
            }

            int back = start.node + 1;
            if(back<=100000 && time[back] > time[start.node]+1){
                time[back] = time[start.node]+1;
                queue.add(new Node(back,time[back]));
            }
        }

        System.out.println(time[K]);
    }

    static class Node implements Comparable<Node>{
        int node;
        int weight;

        Node(int node,int weight){
            this.node = node;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    }
}