[LeetCode] 743. Network Delay Time

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

1에서 n까지 레이블이 지정된 n 개의 노드로 구성된 네트워크가 제공됩니다. 또한 시간, 이동 시간 목록을 지정 에지로 제공합니다. times [i] = (ui, vi, wi), 여기서 ui는 소스 노드, vi는 대상 노드, wi는 걸리는 시간입니다. 소스에서 타겟으로 이동합니다. 주어진 노드 k에서 신호를 보냅니다. 모든 n 개의 노드가 신호를 수신하는 데 걸리는 시간을 반환합니다. n 노드가 모두 신호를 수신 할 수없는 경우 -1을 반환합니다.

✍️ 풀이

---

다익스트라 알고리즘을 통해 풀이.
다익스트라 정리

🛠 코드

---

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        
        for a, b, cost in times:
            graph[a].append((b, cost))
        
        q = [(0, k)]
        dist = collections.defaultdict(int)
        
        while q:
            time, node = heapq.heappop(q)
            if node not in dist:
                dist[node] = time
                for v, w in graph[node]:
                    alt = time + w
                    heapq.heappush(q, (alt, v))
        print(dist)
        if len(dist) == n:
            return max(dist.values())
        return -1
        
            

---

📝 정리

---

🎈 참고

---

Book 링크