접근
일반적인 다익스트라 알고리즘을 적용해 풀 수 있는 문제. 다만 모든 노드를 방문했는지 확인해야 되는 예외처리 부분이 포인트라고 생각한다. 자바스크립트에서는 클래스를 직접 구현해야하므로 코드는 생략한다.
Python
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
graph = [[] for i in range(n+1)]
# graph 생성
for [cur_v, next_v, weight] in times:
graph[cur_v].append((weight, next_v))
# visited cost 딕셔너리
costs = {}
# Priority Queue
pq = []
heapq.heappush(pq, (0, k))
while pq:
[cur_cost, cur_v] = heapq.heappop(pq)
# 방문한 적이 없는 경우
if cur_v not in costs:
costs[cur_v] = cur_cost
# graph에서 연결된 노드 다 가져오기
for (cost, next_v) in graph[cur_v]:
# 다음 경로의 cost 계산
next_cost = cur_cost+cost
heapq.heappush(pq, (next_cost, next_v))
# 모든 노드를 돌았는지 확인
result = -1
for i in range(1, n+1):
if i not in costs:
return -1
result = max(result, costs[i])
return result
print(f"==>> Solution: {Solution().networkDelayTime(
[[1, 2, 1], [2, 1, 3]], 2, 2)}")
Python
복사