[백준 1800번] 인터넷 설치 (Python3)

import sys
input = sys.stdin.readline
from heapq import heappush,heappop
INF=1e9

N,M,K = map(int,input().split())

graph = [[] for i in range(N)]
for i in range(M):
  x,y,w = map(int,input().split())
  graph[x-1].append((y-1,w))
  graph[y-1].append((x-1,w))

DP = [[INF]*N for i in range(K+1)]
hq = []
heappush(hq,(0,0))
while hq:
  w,now = heappop(hq)
  if DP[0][now] <= w:
    continue
  DP[0][now] = w
  for next,w1 in graph[now]:
    heappush(hq,(max(w,w1),next))
for k in range(1,K+1):
  hq = []
  heappush(hq,(0,0))
  while hq:
    w,now = heappop(hq)
    if DP[k][now] <= w:
      continue
    DP[k][now] = w
    for next,w1 in graph[now]:
      heappush(hq,(DP[k-1][now],next))
      heappush(hq,(max(w,w1),next))

if DP[K][N-1] == INF:
  print(-1)
else:
  print(DP[K][N-1])

도로포장 [백준 1162번] 도로포장 (Python3) (tistory.com) 문제와 똑같은 방식으로 해결하였다.

 

도로포장 문제의 경우 K의 범위가 20이고, 이 문제는 K의 범위가 N까지이기 때문에 시간복잡도상 풀리지 않을 것이라고 예상하였는데, 막상 제출하니 잘만 통과되었다. 다 익스트라의 시간복잡도가 ElogE라고 알고 있어서, 시간복잡도가 K*ElogE가 될 것 같은데, 데이터가 약한 탓인지 아니면 다른 요인이 작용을 한 것인지 모르겠다.

 

풀이는, 도로포장 문제에서 값을 갱신하는 방식만 w+w1이 아닌 max(w,w1)으로 바꿔주면 된다. 다른 점이 하나도 없다.

 

 

오늘의 교훈) 다 익스트라의 시간복잡도에 대해서 고민해보자