📌 문제
- 파이썬 알고리즘 인터뷰 40번 문제
- 최단 경로 탐색: 다익스트라 알고리즘 활용
📌 날짜
2020.02.13
📌 시도 횟수
5 try / Failed
💡 정답 Code
from collections import defaultdict
import heapq
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
graph = defaultdict(list)
for n1, n2, sec in times:
graph[n1].append((n2, sec))
Q = [(0, k)]
dist = defaultdict(int)
while Q:
time, node = heapq.heappop(Q)
if node not in dist:
dist[node] = time
for n2, sec in graph[node]:
alt = time + sec
heapq.heappush(Q, (alt, n2))
if len(dist) == n:
return max(dist.values())
return -1
💡 문제 해결 방법
- 아래의 과정을 천천히 이해해보자.
- 파이썬의 heapq는 min heap의 결과를 저장한다는 점!
- 따라서 "최소 힙부터 pop"되므로 time이 높은 값은 결국 나중에
"dist에 이미 값이 존재한다고 판단"되므로 버려지게 된다는 점을 유의하자.
- graph를 생성하면 다음과 같다.
- Q와 dist를 생성하고 초기화한다.
heapq.heappop(Q)한 결과를 dist에 저장한다.
- 방금 heappop한 Q의 node와 인접한 노드들을 Q에 넣는다.
이때 새롭게 Q에 넣는 인접한 노드들의 time 값은,
"이전의 연결된 노드(3)의 time 값(0)" + "graph에 저장된 sec값"이 되도록 한다.
즉, 이전에 연결된 노드들의 time값도 더해져서 누적된 값을 Q에 넣는 time 값이 되도록 한다.
- 다시 heappop해서 dist에 넣는다.
- 다시 heappop한 노드와 인접한 노드들을 Q에 추가한다.
마찬가지로 Q에 추가할 때에는 해당 인접한 노드의 time 값이 이전 노드의 time값을 합친 누적값이 되도록 한다.
- graph[4]의 sec는 1이지만, dist[4]의 time이 1이므로, 따라서 최종적으로 (node = 1, time = 1+1 = 2)를 Q에 추가함.
- 계속 위의 과정을 반복
- 만약 Q에서 heappop한 것의 node가 이미 dist에 존재한다면 과감히 버리고 넘어간다.
- 따라서 최종 결과는
dist = {3: 0, 4: 1, 1: 2, 2: 2}
이고 len(dist) == n
이므로 dist의 value(time) 값들의 max 값인 2를 리턴한다.
💡 새롭게 알게 된 점
- 다익스트라 알고리즘의 형태와 활용에 대해 조금 이해하게 되었다.
- 이런 풀이의 형태에 좀 더 익숙해져야겠다.
❌ (한번에 맞추지 못한 경우) 오답의 원인
- ㅎㅎ 최단 경로 문제 처음 풀어봤다.
bfs를 이리저리 바꿔봤지만 계속 오류가 나서 결국 책을 봤다😹