[백준] 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개를 0으로 바꿀 수 있기 때문에 조금 생각이 필요한 문제였다.
• 예적 BFS의 벽부수기 문제와 비슷하게 비용을 담는 weights 배열을 2차원으로 만들어서 각각의 도로까지 오는데 걸린 비용이 포장되지 않았을 때, 1번 포장 되었을 때, 2번 포장되었을 때, k번 포장되었을 때를 담도록 한다.

import sys, heapq

def dijkstra(start):
    heap, INF, cnt = [], sys.maxsize, 0
    weights = [[INF] * (k+1) for _ in range(n+1)]
    heapq.heappush(heap, (0, start, cnt))
    weights[start][cnt] = 0
    while heap:
        weight, node, cnt = heapq.heappop(heap)
        if weights[node][cnt] < weight:
            continue

        for next_node, cost in adj[node]:
            tmp = weight + cost
            if weights[next_node][cnt] > tmp:
                weights[next_node][cnt] = tmp
                heapq.heappush(heap, (tmp, next_node, cnt))

            if cnt < k and weights[next_node][cnt+1] > weight:
                # 여기서 도로 포장!
                weights[next_node][cnt+1] = weight
                heapq.heappush(heap, (weight, next_node, cnt+1))
    return min(weights[n])

n, m, k = map(int, input().split())
adj = [[] for _ in range(n+1)]

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    adj[a].append((b,c))
    adj[b].append((a,c))

print(dijkstra(1))