백준 1162 : 도로포장 (Python)

본문 링크

import sys, heapq
input = sys.stdin.readline
INF = float('inf')


def Dijkstra():
    dp[0][0] = 0
    heap = [] ; heapq.heappush(heap, (0, 0, 0))

    while heap:
        value, node, height = heapq.heappop(heap)
        if dp[height][node] < value:
            continue

        for next_value, next_node in graph[node]:
            next_value += value

            if next_value < dp[height][next_node]:
                dp[height][next_node] = next_value
                heapq.heappush(heap, (next_value, next_node, height))

            if height + 1 <= K and value < dp[height + 1][next_node]:
                dp[height + 1][next_node] = value
                heapq.heappush(heap, (value, next_node, height + 1))


N, M, K = map(int, input().split())
graph = [[] for _ in range(N + 1)]

for i in range(M):
    A, B, C = map(int, input().split())
    graph[A - 1].append((C, B - 1))
    graph[B - 1].append((C, A - 1))  # 양방향

dp = [[INF] * (N + 1) for _ in range(K + 1)]
Dijkstra()
Answer = float('inf')
for i in range(K + 1):
    Answer = min(Answer, dp[i][N - 1])

print(Answer)

📌 어떻게 접근할 것인가?

다익스트라를 통해 풀었습니다.
이때 dp 배열을 2차원으로 선언해서 K 개의 포장도로를 만드는 최소값을 항상 갱신해주어야 합니다.

if height + 1 <= K and value < dp[height + 1][next_node]:
	dp[height + 1][next_node] = value
	heapq.heappush(heap, (value, next_node, height + 1))

만약 도로를 포장하는 것이 가능하고 그때 값이 더 줄어들 수 있다면
dp 배열에 기존의 값을 그대로 넣어줍니다.
dp[x][y] 라고 할때 x 는 포장한 도로의 개수 , y 는 지금까지 이동한 거리의 최소값을 담았습니다.

이때 next_value 가 아니라 value 값을 넣어주어여 합니다.

또 중요한 것은

INF = float('inf') #INF=int(1e9) 시 틀림

문제에서 주어지는 수의 범위가 매우 크기 때문에 최대값을 다음과 같이 잡아주셔야 합니다.

다익스트라에서 최소값을 갱신하는 과정에서 특정 K 개의 도로를 0 으로 만들 수 있을때 2차원 배열을 이용해서 최소값을 찾을 수 있습니다.