[백준] 1162 도로포장 파이썬

문제

1162번: 도로포장

풀이

1. 서울에서 시작하여 포천까지 최소 시간이 걸리도록 해야합니다.

2. 도시별로 최소 시간을 구하기 위해서  다익스트라 알고리즘을 구현합니다.

3. 주의할 점은 K개를 사용해서 거리를 포장하면 시간이 0이 되기 때문에 이 부분을 구현해야 합니다.

4. 구현하는 방법은 도시별의 최소 시간과 도시별 방문 유무 리스트를  2차원(N * K)으로 늘려주면 됩니다. 포천에서 1 ~ K번 포장했을 때의 최단시간을 구해주고 그중 최소 시간을 구해야 하기 때문입니다.

 

코드

import sys
import heapq

INF = sys.maxsize
input = sys.stdin.readline
N, M, K = map(int, input().split())
K += 1

# N * K 배열로 만듦
vstd = [[False] * K for _ in range(N)]
dist = [[INF] * K for _ in range(N)]

adj = [[] for _ in range(N)]

# 양방향 도로이기 때문에 u -> v, v -> u로 도로를 추가
for _ in range(M):
    u, v, w = map(int, input().split())
    adj[u - 1].append((v - 1, w))
    adj[v - 1].append((u - 1, w))

h = []
heapq.heappush(h, (0, 0, K - 1))

# 서울에서의 모든 시간은 0으로 초기화
for i in range(K):
    dist[0][i] = 0

while h:
    _, curr, k = heapq.heappop(h)
    
    #현재 도시에서 k번 포장한 최단거리를 이미 방문했다면 continue
    if vstd[curr][k]:
        continue
    vstd[curr][k] = True
    
    for nxt, d in adj[curr]:
        if dist[curr][k] + d < dist[nxt][k]:
            dist[nxt][k] = dist[curr][k] + d
            heapq.heappush(h, (dist[nxt][k], nxt, k))
            # 포장을 할 수 있고 다음 도로보다 시간이 짧다면 포장해줌
            if k > 0:
                if dist[nxt][k - 1] > dist[curr][k]:
                    dist[nxt][k - 1] = dist[curr][k]
                heapq.heappush(h, (dist[nxt][k - 1], nxt, k - 1))
                
# 포천에서의 1-k번 사용했을 때의 최소 시간 중 최소값이 결과값
print(min(dist[-1]))