숨바꼭질 3

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

풀이

문제의 핵심은 수빈이가 X에 있다면 수빈이가 X-1, X+1의 위치로 가는데 드는 비용은 1이고, 2*X의 위치로 가는데 드는 비용은 0이라는 점이다.

이를 그래프로 표현해서 다익스트라 알고리즘을 이용하면 풀린다?

맞다. 여기서 그래프로 표현할 때 주의할 점은 수빈이의 위치보다 동생의 위치가 작을 수 있다는 점이다. 따라서 그래프의 최대 노드 개수는

max(N,K) + 2

이다. +2를 하는 이유는 최대가 10만일 때 만들어지는 노드가 100002까지이기 때문이다.

0부터 시작하는데 0같은 경우 0초 후 위치는 0이기때문에 무시하고 0에서 1로 가는 경로를 저장하고 1은 2로 가는 경로의 비용이 1인 경우와 0인 경우가 있는데 더 작은 비용인 0인 경우를 선택하여 저장한다. 2부터는 ±1인 위치로 가는 경로는 비용을 1로 저장한다.

2배인 위치로 이동하는 경로는 0을 저장하는데, 이때 2배인 경로를 저장하는 것은 max(N,K) + 1/2 로 나눈 값까지만 저장한다.

만약 N 또는 K가 10만일 경우 따로 제한을 안 걸면 20만까지 노드를 만들어 탐색을 해야는데 이는 메모리 낭비이기 때문에 제한을 걸어준다.

이렇게 그래프를 만드는 것이 끝났다면 시작점을 N으로 해서 다익스트라 알고리즘으로 경로를 구하고 거기서 도착점이 K인 값을 가져오면 답을 구할 수 있다.

import java.io.*;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int n, m;
    static ArrayList<Pair>[] graph;
    static PriorityQueue<Pair> queue;
    static int len;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        len = Math.max(n, m);
        graph = new ArrayList[len + 3];
        queue = new PriorityQueue<>();

        for (int i = 0; i <= len + 2; i++) {
            graph[i] = new ArrayList<>();
        }
        graph[0].add(new Pair(1, 1));
        graph[1].add(new Pair(0, 1));
        graph[1].add(new Pair(2, 0));

        int limit = len / 2 + 1;

        for (int i = 2; i <= len + 1; i++) {
            graph[i].add(new Pair(i - 1, 1));
            graph[i].add(new Pair(i + 1, 1));
            if (i <= limit)
                graph[i].add(new Pair(i * 2, 0));
        }

        int[] dist = dijkstra(n);

        bw.write(dist[m] + "\n");
        bw.close();
        br.close();
    }

    private static int[] dijkstra(int start) {
        int[] dist = new int[len + 3];
        boolean[] visited = new boolean[len + 3];

        for (int i = 0; i <= len + 2; i++) {
            if (i == start)
                dist[i] = 0;
            else
                dist[i] = Integer.MAX_VALUE;
        }

        queue.offer(new Pair(start, 0));
        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            int y = p.y;
            if (visited[y])
                continue;
            else
                visited[y] = true;

            for (Pair next : graph[y]) {
                if (dist[next.y] >= dist[y] + next.weight) {
                    dist[next.y] = dist[y] + next.weight;
                    queue.offer(new Pair(next.y, dist[next.y]));
                }
            }
        }
        return dist;
    }

}

class Pair implements Comparable<Pair> {
    public int y;
    public int weight;

    public Pair(int y, int weight) {
        this.y = y;
        this.weight = weight;
    }

    @Override
    public int compareTo(Pair o) {
        return Integer.compare(this.weight, o.weight);
    }
}