BOJ 1162 도로포장

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

문제

준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다.

문제는 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 도로는 이미 있는 도로만 포장할 수 있고, 포장하게 되면 도로를 지나는데 걸리는 시간이 0이 된다. 또한 편의상 서울은 1번 도시, 포천은 N번 도시라 하고 1번에서 N번까지 항상 갈 수 있는 데이터만 주어진다.

---

입력

첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하는데 걸리는 시간이 주어진다. 도로들은 양방향 도로이며, 걸리는 시간은 1,000,000보다 작거나 같은 자연수이다.

---

출력

첫 줄에 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.

---

예제 입력 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

예제 출력 1

1

---

코드

이번 문제는 일반적인 다익스트라 문제에서 도로를 포장해 K개의 간선의 가중치를 0으로 만들 수 있다는 DP 개념을 추가한 문제이다.

대략적인 코드는 맞았지만 두 가지를 간과해 많은 시도 후에 AC를 받을 수 있었다.

간과한 점은 다음과 같다.

1. 다익스트라로 특정 위치를 검사할 때 이미 이전에 더 낮은 비용으로 방문한 곳이면, 그 위치에 연결된 모든 간선을 검사할 필요 없이 다음 위치를 검사하는 것이 효율적이라는 점
2. 포장할 도로의 수 K가 도로의 수 M보다 클 수 있다는 점

간과한 부분은 아래 코드에 주석을 달았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class Edge {
        // 도착 도시의 번호를 저장하기 위한 end, 포장된 도로 수를 저장하기 위한 paved
        int end, paved;
        long cost;

        public Edge(int end, long cost) {
            this.end = end;
            this.cost = cost;
        }

        public Edge(int end, long cost, int paved) {
            this.end = end;
            this.cost = cost;
            this.paved = paved;
        }
    }

    static int N, M, K;
    /**
     * 첫 번째 인덱스는 도착지를 의미, 두 번째 인덱스는 검사 시점까지 포장된 도로의 수를 의미
     * 예를 들면, dp[3][2]는 2개의 포장된 도로가 있을 때, 3번 지역까지 가는 최소 시간을 의미
     */
    static long[][] dp;
    static ArrayList<Edge>[] edges;

    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());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        edges = new ArrayList[N + 1];
        dp = new long[N + 1][K + 1];
        for (int i = 1; i <= N; i++) {
            edges[i] = new ArrayList<>();
            Arrays.fill(dp[i], Long.MAX_VALUE);
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()),
                end = Integer.parseInt(st.nextToken()),
                cost = Integer.parseInt(st.nextToken());

            edges[start].add(new Edge(end, cost));
            edges[end].add(new Edge(start, cost));
        }

        dijkstra();

        /**
         * 간과한 포인트 2
         * 포장할 도로의 수 K가 도로의 수 M보다 클 경우
         * M개의 도로만 포장할 수 있기 때문에 dp[N][M]을 출력
         * 그 외에는 간선의 가중치를 하나라도 더 0으로 만드는 것이
         * 시간을 단축할 수 있기 때문에 dp[N][K]를 출력
         */
        System.out.println(K > M ? dp[N][M] : dp[N][K]);
    }

    static void dijkstra() {
        PriorityQueue<Edge> queue = new PriorityQueue<>(Comparator.comparingLong(edge -> edge.cost));
        queue.offer(new Edge(1, 0, 0));
        dp[1][0] = 0;

        while (!queue.isEmpty()) {
            Edge check = queue.poll();

            /**
             * 간과한 포인트 1
             * 이전에 해당 위치에 방문했을 때 이미 더 낮은 비용으로 왔다면
             * 해당 위치에서 간선(도로)으로 이어진 노드 역시 더 낮은 비용으로 dp에 저장돼있기 때문에
             * 연결된 모든 간선을 검사하지 않고 스킵
             */
            if (dp[check.end][check.paved] < check.cost)
                continue;

            // 현재 위치에서 갈 수 있는 모든 도로를 검사
            for (Edge toMove: edges[check.end]) {
                // 검사 중인 도로를 포장했을 때의 최소 비용 계산
                if(check.paved < K && dp[toMove.end][check.paved + 1] > check.cost) {
                    dp[toMove.end][check.paved + 1] = check.cost;
                    queue.offer(new Edge(toMove.end, check.cost, check.paved + 1));
                }

                // 검사 중인 도로를 포장하지 않았을 때의 최소 비용 계산
                if(dp[toMove.end][check.paved] > check.cost + toMove.cost) {
                    dp[toMove.end][check.paved] = check.cost + toMove.cost;
                    queue.offer(new Edge(toMove.end, dp[toMove.end][check.paved], check.paved));
                }
            }
        }
    }
}