[LeetCode] 743. Network Delay Time

😎풀이

1. 그래프 구성
2. 각 노드로 가는 최단기 거리 초기화(1-Indexed 이므로 0은 -1로 예외 초기화)
3. BFS 형식으로 순회
   3-1. 현재 조건보다 단기로 목표 지점에 갈 수 있다면 생략
   3-2. 이웃 노드를 현재 노드로 경유해서 가는 방법이 더 빠르다면 갱신
4. 가장 오래 걸리는 시간 = 모든 노드를 경유하는데 필요한 시간
5. 초기화 값을 가진 노드가 있다면, 경유 불가 이므로 -1 반환

function networkDelayTime(times: number[][], n: number, k: number): number {
    const graph = new Map<number, { to: number, signal: number }[]>()
    for(const [u, v, w] of times) {
        graph.set(u, [...(graph.get(u) ?? []), { to: v, signal: w }])
    }
    const dist = Array(n + 1).fill(Infinity)
    dist[0] = -1
    dist[k] = 0
    const queue = [[0, k]]
    while(queue.length) {
        const [time, node] = queue.shift()
        if(dist[node] < time) continue
        const neighbor = graph.get(node) ?? []
        for(const { to, signal } of neighbor) {
            if(dist[to] <= dist[node] + signal) continue
            dist[to] = dist[node] + signal
            queue.push([dist[to], to])
        }
    }
    const maxTime = Math.max(...dist)
    if(maxTime === Infinity) return -1
    return maxTime
};