백준 1162번: 도로포장 (Java)

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

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개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.

 

---

 

K <= 20인 걸 보고, 처음에는 '다익스트라를 돌려 경로 추적을 하여 해당 경로에서 가장 긴 구간을 포장하는 과정을 반복한다'는 그리디적인 풀이법을 생각해냈다. 근데 예제보니 바로 아니더라ㅎㅎ;;

그러다가 살짝 더 생각해보니, '말이 되고픈 원숭이(https://www.acmicpc.net/problem/1600)'적인 풀이법이 생각났다.

 

풀이

d[i][j]: j번 포장하여 i번째로 도시로 가는 최소 거리

다익스트라를 돌리되, 1) 포장 안하고 가기 2) 포장 하고 가기 둘 다 체크해준다.

시간복잡도는 대략 O(NlogN*K)다.

 

배운 점

최솟값을 그냥 d[N][K]로 출력했는데, '도시가 2개이고 K=2인 경우'를 생각해보면 d[2][1] = 0, d[2][2] = (1부터 2 사이의 거리)가 나오게 된다. 아이디어부터 구현까지 다 잘했는데, 끝까지 집중하여 구현하자.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static final long INF = Long.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Edge>());
        }
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());
            graph.get(u).add(new Edge(v, dist, 0));
            graph.get(v).add(new Edge(u, dist, 0));
        }
        
        long[][] d = new long[N+1][K+1];
        for (int i = 0; i < N+1; i++) {
            Arrays.fill(d[i], INF);
        }
        
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(1, 0, 0));
        d[1][0] = 0;
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            if (d[cur.loc][cur.paveCnt] < cur.dist) continue;
            for (Edge nxt: graph.get(cur.loc)) {
                if (d[nxt.loc][cur.paveCnt] > cur.dist + nxt.dist) {
                    d[nxt.loc][cur.paveCnt] = cur.dist + nxt.dist;
                    pq.offer(new Edge(nxt.loc, cur.dist + nxt.dist, cur.paveCnt));
                }
                if (cur.paveCnt < K) {
                    if (d[nxt.loc][cur.paveCnt+1] > cur.dist) {
                        d[nxt.loc][cur.paveCnt+1] = cur.dist;
                        pq.offer(new Edge(nxt.loc, cur.dist, cur.paveCnt+1));
                    }
                }
            }
        }
        long ans = INF;
        for (int k = 0; k <= K; k++) {
            if (ans > d[N][k]) ans = d[N][k];
        }
        System.out.println(ans);
    }
    
    static class Edge implements Comparable<Edge> {
        int loc;
        long dist;
        int paveCnt;
 
        public Edge(int loc, long dist, int paveCnt) {
            this.loc = loc;
            this.dist = dist;
            this.paveCnt = paveCnt;
        }
 
        public int compareTo(Edge o) {
            return Long.compare(this.dist, o.dist);
        }
    }
}