[LeetCode] 743. Network Delay Time - BFS

문제 링크 : https://leetcode.com/problems/network-delay-time/

Network Delay Time - LeetCode

743. Network Delay Time

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Example 1

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

Note:

1. N will be in the range [1, 100].
2. K will be in the range [1, N].
3. The length of times will be in the range [1, 6000].
4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

---

풀이

이 문제는 해당 노드에 얼마나 시간이 걸리는지를 확인해야하는 문제였습니다. visited 배열에 시간이 얼마나 걸렸는지를 넣어주는 형식의 문제죠.

Main Idea는 아래와 같습니다.

1. BFS를 이용한다
2. 배열 t => 그 노드를 방문하는데 걸리는 최소 시간. 초반의 모든 원소를 float('inf') (무한을 나타냄)로 시작해서 줄여나가는 방식을 택합니다.

from collections import deque
class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        t = [0] + [float('inf')] * N
        graph = collections.defaultdict(list)
        q = collections.deque()

        for u, v, w in times:
            graph[u].append((v, w))

        q.append((0, K))

        while q:
            time, node = q.popleft()
            if time < t[node]:
                t[node] = time
                for v, w in graph[node]:
                    q.append((time + w, v))

        mx = max(t)

        if mx < float('inf'):
            return mx
        else:
            return -1