[백준] 1162번, 도로포장 (Python)

문제

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

1162번: 도로포장

 

코드

import heapq
import sys
input = sys.stdin.readline
INF = sys.maxsize
n, m, k = map(int, input().split())

graph = [[] for _ in range(n+1)]
distance = [[INF for _ in range(k+1)] for _ in range(n+1)] # 도로를 몇개 포장했는지 확인하기 위해서 이중리스트로 만든다.
for i in range(m):
    x,y,z = map(int,input().split())
    graph[x].append((z,y))
    graph[y].append((z,x))

def dijkstra(start):
    queue = []
    cnt = 0
    distance[start][cnt] = 0
    heapq.heappush(queue, (0, start, cnt))

    while queue:
        wei, now, cnt = heapq.heappop(queue)
        if distance[now][cnt] < wei:
            continue
        for w, next_node in graph[now]:
            next_wei = w + wei
            if distance[next_node][cnt] > next_wei:
                distance[next_node][cnt] = next_wei
                heapq.heappush(queue, (next_wei, next_node,cnt))
                
            # elif로 안하고 if로 하는 이유는 모든곳을 돌아 도로포장을 했을때 가장 작은 값을 찾기 위해서이다.
            if cnt < k and distance[next_node][cnt+1] > wei: 
            # 도로포장 횟수가 남았고 현재까지 distance[next_node][cnt+1](next_node 까지 가중치)가 wei(now 노드까지 가중치)보다 크다면 
            # next_node까지 움직이는 w(now에서 next_node까지 가중치)를 무시하고 wei를 넣어준다.
                distance[next_node][cnt+1] = wei
                heapq.heappush(queue, (wei, next_node, cnt+1))


dijkstra(1)
print(min(distance[n]))

가중치가 주어지고 특정지점까지 가장 짧은 경로를 구하는 문제로 다익스트라 문제이다.

 

처음에 도로포장을 해주는것을 어떻게 표현해야 할지 몰라 검색을 했다..

distance 리스트를 이중리스트로 만들어 도로포장을 몇번했는지에 따라 값을 저장한다.

 

다익스트라를 수행하는데 도로포장 횟수가 아직 남았고 현재노드 까지 가중치보다 다음 노드까지 저장된 가중치가 크다면 도로포장을 해준다.

 

도로포장을 할 수 있는 모든 곳에서 도로포장을 했을때 가장 작은 시간이 걸리는 값을 출력한다.