[LeetCode] 743. Network Delay Time [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Network Delay Time - LeetCode>

1. 문제 (네트워크 딜레이 타임)

k부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다.

입력값 (x,y,z)는 각각 출발지, 도착지, 소요 시간으로 구성되며, 전체 노드의 개수는 n으로 입력받는다.

2. 풀이

다익스트라 알고리즘을 이용한 풀이

3. 코드

from collections import defaultdict
import heapq
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = defaultdict(list)
        for x, y, w in times:
            graph[x].append((y, w))

        dist = defaultdict(int)
        q = [(0, k)]
        while q:
            time, node = heapq.heappop(q)
            if node not in dist:
                dist[node] = time
                for x, y in graph[node]:
                    temp = time + y
                    heapq.heappush(q, (temp, x))

        if len(dist) == n:
            return max(dist.values())
        return -1

• 결과 :

방식	Status	Runtime	Memory	Language
그래프 (DFS)	[Accepted]	640 ms	16.4 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋