[Python 3] BOJ - 1162 "도로포장"

 # 문제 링크

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

1162번: 도로포장

 

 # 풀이

 개인적으로 이 문제의 핵심은 2차원 다익스트라 알고리즘이라고 생각한다. 일반적으로 다익스트라 알고리즘은 1차원 배열이지만, 이 문제에는 정점과 또 다른 정보인 포장 횟수가 있으며 포장 여부에 따라 간선의 가중치가 달라지기 때문에 1차원으로 설정한다면 포장에 대한 정보를 알 수 없다. 따라서, 포장을 시키지 않는 경우를 기본적으로 검사한 후, 포장할 여력이 있다면 포장을 시키면서 최소 거리를 찾으면 정답을 구할 수 있다.

 

 # 코드

import sys, heapq

# 입력부
n,m,k = map(int, sys.stdin.readline().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))
    
# inf : 임의의 무한대값
inf = 98765432109876543210

# d : 2차원 다익스트라 배열. 현재 정점 i에서 포장을 j개 했을 때 드는 최소거리
d = [[inf] * (k + 1) for _ in range(n + 1)]
q = []
for i in range(k + 1):
    d[1][i] = 0
heapq.heappush(q, (0,1,0))

# 다익스트라 
while q:
    now_dist, now, p = heapq.heappop(q)
    if d[now][p] < now_dist:
        continue
    # 현재 정점에서 포장이 가능한 경우
    if p + 1 <= k:
        for (next, next_dist) in adj[now]:
            if d[next][p + 1] > now_dist:
                d[next][p + 1] = now_dist
                heapq.heappush(q, (now_dist, next, p + 1))
                
    # 기본적으로 포장을 하지 않는 경우
    for (next, next_dist) in adj[now]:
        if d[next][p] > now_dist + next_dist:
            d[next][p] = now_dist + next_dist
            heapq.heappush(q, (now_dist + next_dist, next, p))
            
# 정답 출력
ans = inf
for i in range(k + 1):
    ans = min(ans, d[n][i])
print(ans)