1 minute read

문제

접근 방법

도로 포장을 하면 그 도로의 거리가 0이 되기 때문에 어떤 도로를 포장하는지에 따라 N번까지의 최소 거리가 달라진다.

우선, 1 -> N 까지의 최소 거리가 중요한 것이기 때문에 Dijkstra를 사용하기로 하였다.

도로 포장을 했을 때와 안 했을 때, 몇번을 해야지 최적인지 등 완전탐색으로 다 따져보기에는 너무 많은 경우의 수가 있기에 다른 탐색 방법을 생각해야 했다. 생각한 방법은 DP를 사용하는 것이다.

2차원 배열을 사용하여 dp[i][j] $\rightarrow$ 도로 포장을 j번 하여 도시 i에 가는 최소 거리를 저장한다.

정답 코드

import sys
import heapq
from collections import deque
input = sys.stdin.readline

"""
지금까지 포장한 도로의 수를 state으로 저장하면서 DP를 해야 할 거 같음

dp[n][k] : n에 오면서 k개의 도로를 포장했을 때의 최소 거리

"""

n,m,k = map(int,input().split())

graph = [[] for _ in range(n+1)]

for _ in range(m):
  a,b,c = map(int, input().split())
  graph[a].append((b,c))
  graph[b].append((a,c))

def dijkstra():
  q = []
  INF = float('inf')
  heapq.heappush(q, (0,1,0))
  dp = [[INF]*(k+1) for _ in range(n+1)]

  for i in range(k+1):
    dp[1][i] = 0

  while q:
    mid_dist, mid_node, nums = heapq.heappop(q)
    if dp[mid_node][nums] < mid_dist:
      continue

    for end_node, end_dist in graph[mid_node]:
      # 도로 포장을 할 수 있다면
      if nums < k:
        new_dist = mid_dist
        #포장했을 때가 더 짧다면, distance update
        if new_dist < dp[end_node][nums+1]:
          dp[end_node][nums+1] = new_dist
          heapq.heappush(q, (new_dist, end_node, nums+1))
      
      #도장 포장 안 했을 때의 최소 거리도 계산
      new_dist = mid_dist+end_dist
    
      #이 거리가 더 짧다면, 최소 거리 update
      if new_dist < dp[end_node][nums]:
        dp[end_node][nums] = new_dist
        heapq.heappush(q, (new_dist, end_node, nums))
        

  
  return dp

dp = dijkstra()

print(min(dp[n]))

You May Also Enjoy