[백준 1162 도로포장] 자바 (다익+DP)

1162번: 도로포장 (acmicpc.net)

1162번: 도로포장

 

 다익스트라 + dp

이전에 **미확인 도착지 문제**를 통해 다익스트라의 기본 형태를 구현했었다.

도로포장은 다익스트라에 dp 를 곁들인 문제다 😐

문제를 간단히 요약하면,

양방향 그래프가 주어지면

1번 노드에서 N 번 노드로 최단 경로로 움직여야 한다.

이때, 좀 더 빠르게 움직이기 위해 **도로 포장** 을 k 번 수행할 수 있다.

도로 포장을 수행하면, 해당 도로의 가중치를 0으로 만들어버린다.

우리가 구해야 하는 것은,

주어진 k 번 이하의 도로 포장을 수행했을 때 목적지에 도달할 수 있는 최단 경로를 반환하면 된다.

(도로 포장을 한 번도 안하는 게 최단 경로일 수도 있다.)

---

다익스트라에서는 dist 배열을 1차원으로 선언하여, 각 노드까지의 최단경로를 저장했다.

하지만 이번에는 도로를 포장했는지, 했다면 몇 번 했는지 까지 고려한 최단 경로를 계산해야한다.

dist 배열을 생각해보면, 다익스트라를 통해 노드를 탐색하면서 계속 update 한다.

지금까지 걸어온 최단경로(sub problem)와 앞으로 갈 최단경로를 비교하여 update 해서 최종적인 경로를 얻는다. -> 여기서 dp 의 개념이 첨가된 것을 알 수 있다.

우리는 여기서 하나 더 나아가서

최단경로를 계산할 때, 앞으로 갈 도로를 포장하는 케이스와 하지 않는 케이스를 모두 고려해야 한다.

이는 어떻게 구현할 수 있을까..?

사실, 접해보지 않으면 떠올리기 힘든 것 같다..

답은 i 번 노드에 도달했을 때까지의 도로 포장 횟수를 고려해야 하므로

dist 배열에 도로 포장 횟수를 나타내는 차원을 추가하고

Node 에도 도로 포장 횟수를 나타내는 필드를 추가하는 것이다.

일반적으로 다익스트라는 아래와 같이 동작한다.

while(pq가 빌때까지){
    now 는 현재  내가 서 있는 노드
    for( now 와 연결된 노드 iter 을 탐색) {
      if( now 에서 iter 으로 가는게 최단 경로이면){
          iter 까지의 최단경로를, now 까지의 최단경로 + iter 의 가중치로 갱신
          pq 에 추가
      }
    }

여기서 포장 횟수를 따로 고려하면,

while(pq가 빌때까지){
    now 는 현재  내가 서 있는 노드
    for( now 와 연결된 노드 iter 을 탐색) {
        if( now 의 포장 횟수인 now.cnt 가 k 보다 작아서, 도로를 포장할 수 있다면 && 도로를 포장했을 때 더 빨리 도달할 수 있다면){
            now.cnt+1 만큼 도로 포장을 수행한, iter 까지의 최단경로를 update
            pq 에 추가
        }
        if( now.cnt 가 k 이상이라서 도로를 더이상 포장할 수 없다면 && iter 으로 가는 게 더 짧은 거리라면){
            now.cnt 만큼 도로 포장을 수행한, iter 까지의 최단 경로를 update
            pq 에 추가
        }
    }

위와 같이 다익스트라를 변형하여 구현할 수 있다.



근데 이렇게 하면 대충 40~50% 에서 시간 초과가 뜰 것이다. 🫠

pq 에 너무 많은 노드가 들어간다던가 해서 시간이 오래 걸리는 것일텐데...

이를 방지하기 위해서는 중복된 연산을 줄여주어야 한다.

즉, 탐색하지 않아도 될 노드를 cut 하여 시간을 최적화하는 과정이 하나 더 필요하다는 것이다.

이미 처리한 노드를 처리하지 않도록 조건을 하나 더 추가해야 한다!

 

---

 

import java.io.*;
import java.util.*;

public class Main {
    static int n; // 노드
    static int m; // 엣지
    static int k; // 포장할 도로 개수
    static long[][] dist;
    static ArrayList<Node>[] graph;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(br.readLine());

        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());
        k = Integer.parseInt(stk.nextToken());

        graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            int w = Integer.parseInt(stk.nextToken());
            graph[a].add(new Node(b, w, 0));
            graph[b].add(new Node(a, w, 0));
        }

        dist = new long[n + 1][k + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dist[i], Long.MAX_VALUE);
        }

        dist[1][0] = 0;

        // do dijkstra
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0, 0));
        while (!pq.isEmpty()) {
            Node now = pq.poll();
            if (now.w > dist[now.to][now.cnt])
                continue;
            for (Node iter : graph[now.to]) {
                if (now.cnt < k && dist[iter.to][now.cnt + 1] > dist[now.to][now.cnt]) {
                    dist[iter.to][now.cnt + 1] = dist[now.to][now.cnt];
                    pq.add(new Node(iter.to, dist[iter.to][now.cnt + 1], now.cnt + 1));
                }
                if (dist[iter.to][now.cnt] > dist[now.to][now.cnt] + iter.w) {
                    dist[iter.to][now.cnt] = dist[now.to][now.cnt] + iter.w;
                    pq.add(new Node(iter.to, dist[iter.to][now.cnt], now.cnt));
                }
            }
        }

        long ans = Long.MAX_VALUE;
        for (int i = 0; i <= k; i++) {
            ans = Math.min(dist[n][i], ans);
        }
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
    }

    static class Node implements Comparable<Node> {
        int to;
        long w;
        int cnt;

        public Node(int to, long w, int cnt) {
            this.to = to;
            this.w = w;
            this.cnt = cnt;
        }

        @Override
        public int compareTo(Node o) {
            return (int) (this.w - o.w);
        }
    }
}