[리트코드] 743. Network Delay Time

# 문제 설명

1부터 n까지의 라벨링된 n개의 노드들의 네트워크가 주어지고, u노드에서 v노드로 가는 데 w만큼의 시간이 걸린다는 여행 시간들의 리스트 times[i] = (u_i, v_i, w_i)가 주어진다.

우리가 k라는 노드부터 신호를 보내면, 모든 n개의 노드가 그 신호를 받을 시간을 반환해라.

만약 모든 n개의 노드들이 그 신호를 받는 게 불가능하다면, -1을 반환한다.

 

# 입출력 예시

입력	출력
times = [[2,1,1],[2,3,1],[3,4,1]] n = 4 k = 2	2
times = [[1,2,1]] n = 2 k = 1	1
times = [[1,2,1]] n = 2 k = 2	-1

 

# 코드 풀이

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = {i:[] for i in range(1, n+1)}
        for u, v, w in times:
            graph[u].append((v, w))
        
        dist = {}
        q = [(0, k)] # heapq(w에 따라 정렬) w, v
        while q:
            wx, x = heappop(q) # 가능한 한 경로의 최소 가중치 노드
            if x not in dist:
                dist[x] = wx 
                for y, wy in graph[x]:
                    heappush(q, (dist[x] + wy, y))
        
        if len(dist) == n:
            return max(dist.values())
        return -1

 

# 핵심 포인트

 

 

• 가장 오래 걸리는 노드까지의 최단 시간을 계산해야 하므로 다익스트라 알고리즘을 사용한다.
• 우선순위를 최소 힙으로 구현한 heapq를 사용하여, 최단거리의 노드를 뽑아낸다.
• list로 heapq 사용하려면, heappush(list, x) & heappop(list) 사용
• list를 heapq로 바꿔서 사용하려면, heapq.heapify(list) 로 O(n)시간에 제자리에 heap으로 변환