(Leet Code JS)Network Delay Time

https://leetcode.com/problems/network-delay-time/

Network Delay Time - LeetCode

 

다익스트라 알고리즘 활용.

 

우선 주어진 times 배열을 그래프로 나타내기 위해

n + 1 크기의 graph 2차원 배열을 선언.

또한, 노드 간 걸리는 시간을 dist 배열에 저장하기 위해 n + 1 크기의 1차원 배열을 선언하여 Infinity로 초기화한다.

 

times를 순회하면서 노드를 연결한다.

단방향으로 되어 있기 때문에 graph[start].push([end, cost])만 해도 된다.

 

시작 점은 k이기 때문에 queue에 [시작점 0, 현재 비용 0]을 넣어 시작한다.

 

큐를 모두 다 돌 때까지 while문 반복.

큐의 가장 앞 부분을 꺼내 각각 [currnet, cost]에 저장한다.

그리고 current 노드에 저장되어 있는 모든 경로를 탐색하여 비용이 가장 적게 드는 경로를 갱신하고, queue에 넣어준다.

 

while문이 종료되면 dist 배열을 순회한다.

만약 dist[i] 중 Inifinity가 있다면 모든 노드를 탐색할 수 없다는 뜻이므로 -1을 리턴한다.

그렇지 않다면 dist[i]와 answer 중 최대값을 answer에 저장하여 리턴하면 된다.

const networkDelayTime = (times, n, k) => {
    let answer = 0;
    const graph = Array.from({length: n + 1}, () => Array());
    const dist = Array(n + 1).fill(Infinity);
    const queue = [];
    
    for(let i = 0; i < times.length; i++){
        const [start, end, cost] = times[i];
        
        graph[start].push([end, cost]);
    }
    
    queue.push([k, 0]);
    dist[k] = 0;
    
    while(queue.length){
        const [current, cost] = queue.shift();
        
        for(let i = 0; i < graph[current].length; i++){
            const [next, nextCost] = graph[current][i];
            
            if(dist[next] > dist[current] + nextCost){
                dist[next] = dist[current] + nextCost;
                queue.push([next, nextCost]);
            }
        }
    }
    
    for(let i = 1; i <= n; i++){
        if(dist[i] === Infinity){
            return -1;
        }
        answer = answer < dist[i] ? dist[i] : answer;
    }
    
    return answer;
};