백준 3694 - 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

문제

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

리뷰

다익스트라를 이용해 풀이할 수 있는 문제였다.

거리를 최소화하며 최고 위원(M-1)까지 도달하는 조건은 간단하게 친밀 관계를
그래프로 형상화한 뒤 다익스트라를 이용하여 최단 거리를 도출하면 되었다.

중점이 되는 부분은 다익스트라를 통해 0에서 M-1까지 도달할 수 있는 경로를
역추적해야 한다는 부분이었다. 이를 위해 최단 거리를 도출하며 현재 도달하는 노드의
이전 노드를 저장하는 preNode 배열을 설정하고, 다익스트라 로직 수행시 해당
값을 갱신하도록 구현했다.

로직의 시간복잡도는 다익스트라의 $O(NlogM)$으로 수렴하므로 $N=20$,
$M=20$이고 $T=100$인 최악의 경우에도 무난히 제한 조건 1초를 통과한다.

코드

import static java.lang.Integer.MAX_VALUE;
import static java.lang.Integer.parseInt;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static int[] dist;
    static int[] preNode;
    static List<List<Node>> graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = parseInt(st.nextToken());
            int M = parseInt(st.nextToken());

            graph = new ArrayList<>();
            for (int i = 0; i < M; i++) {
                graph.add(new ArrayList<>());
            }

            dist = new int[M];
            preNode = new int[M];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                int u = parseInt(st.nextToken());
                int v = parseInt(st.nextToken());
                int w = parseInt(st.nextToken());

                graph.get(u).add(new Node(v, w));
                graph.get(v).add(new Node(u, w));
            }

            dijkstra(0);
            Stack<Integer> stack = new Stack<>();
            int node = M - 1;
            while (node != -1) {
                stack.push(node);
                node = preNode[node];
            }

            sb.append("Case #").append(t).append(": ");

            if (dist[M - 1] == MAX_VALUE) {
                sb.append(-1);
            } else {
                while (!stack.isEmpty()) {
                    sb.append(stack.pop()).append(" ");
                }
            }

            sb.append("\n");
        }

        System.out.print(sb);
        br.close();
    }


    static void dijkstra(int start) {
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(preNode, -1);

        dist[start] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.w));
        pq.offer(new Node(start, dist[start]));

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (dist[cur.u] < cur.w) {
                continue;
            }

            for (Node next : graph.get(cur.u)) {
                if (dist[next.u] < dist[cur.u] + next.w) {
                    continue;
                }

                dist[next.u] = dist[cur.u] + next.w;
                preNode[next.u] = cur.u;
                pq.offer(new Node(next.u, dist[next.u]));
            }
        }
    }

    static class Node {
        int u, w;

        public Node(int u, int w) {
            this.u = u;
            this.w = w;
        }
    }
}

결과