백준 13913 - 숨바꼭질 3

문제

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

리뷰

0-1 BFS와 다익스트라로 풀이할 수 있는 숨바꼭질 시리즈 문제이다.

다른 문제와 다르게 이 문제에서 추가된 요구는 최단 경로 비용과 더불어
최단 경로를 출력하는 것이었다. 이를 위해선 최단 경로에 포함되는 정점들을
저장하는 로직이 필요했다.

이를 위해 기존 다익스트라 로직에서 시작점에서 각 정점까지의 최단 경로 비용을
저장하는 dist 배열을 $2 \times N$의 형태로 확장하고, 다익스트라 로직
수행시 최단 경로 비용을 dist[1][N]에, 최단 경로에서 특정 노드 $N$에 도달하기
직전 노드를 dist[0][N]에 갱신하며 저장하는 방식으로 구현하였다.

가장 높은 시간복잡도를 가지는 다익스트라 로직의 시간복잡도가 $O(ElogV)$이므로
정점의 개수가 $100,001$개이고 각 정점당 가능한 간선의 개수는 3개씩이므로
최악의 시간복잡도는 $300,003log(100,000)$ 으로 수렴한다. $log(100,000)$이
5정도이므로 전체 연산량은 150만 가량이라 주어진 문제의 2초 제한 조건을
무난히 통과한다.

코드

import java.util.*;

import static java.lang.Integer.parseInt;


public class Main {
    static int[][] dist;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(in.nextLine());
        int N = parseInt(st.nextToken());
        int K = parseInt(st.nextToken());

        dist = new int[2][100_001];
        dist[0][N] = -1;
        Arrays.fill(dist[1], Integer.MAX_VALUE);

        dijkstra(N, K);
        List<Integer> result = getPath(K);

        System.out.println(dist[1][K]);
        for (int i = result.size() - 1; i >= 0; i--)
            System.out.print(result.get(i) + " ");

        in.close();
    }

    static List<Integer> getPath(int end) {
        List<Integer> result = new ArrayList<>();
        int pre = end;

        while (pre != -1) {
            result.add(pre);
            pre = dist[0][pre];
        }

        return result;
    }


    static void dijkstra(int start, int end) {
        PriorityQueue<Node> pq =
                new PriorityQueue<>(Comparator.comparingInt(n -> n.level));
        dist[1][start] = 0;
        pq.offer(new Node(start, dist[1][start]));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            if (current.vertex == end)
                break;

            if (dist[1][current.vertex] < current.level)
                continue;

            int next = current.vertex - 1;

            if (next >= 0 && dist[1][next] > current.level + 1) {
                dist[1][next] = current.level + 1;
                dist[0][next] = current.vertex;
                pq.offer(new Node(next, dist[1][next]));
            }

            next = current.vertex + 1;

            if (next < dist[0].length && dist[1][next] > current.level + 1) {
                dist[1][next] = current.level + 1;
                dist[0][next] = current.vertex;
                pq.offer(new Node(next, dist[1][next]));
            }

            next = current.vertex * 2;

            if (next < dist[0].length && dist[1][next] > current.level + 1) {
                dist[1][next] = current.level + 1;
                dist[0][next] = current.vertex;
                pq.offer(new Node(next, dist[1][next]));
            }
        }
    }

    static class Node {
        int vertex, level;

        public Node(int vertex, int level) {
            this.vertex = vertex;
            this.level = level;
        }
    }
}

결과