[다익스트라 레벨3] 부대복귀

 

문제링크

 

 

첫번째 풀이 (성공)

 

문제에 정해진 destination에서 다른 부대로 이동하기까지 최소비용을 구한다 => 몇일 전 공부한 다익스트라가 생각났다.

1. 시작노드에서 각 노드까지 최소비용값을 저장할 distance 배열을 만든다
   1. 이 때 인덱스 = 노드값 동일하게 하기 위해 길이는 n+1이다
   2. 최소비용을 구하므로 Infinity로 초기화한다.
2. roads를 순회하며 각 노드에 연결된 neighbors를 정리하여 양방향 그래프 graph를 만든다. (distance와 같은 길이)
3. queue에 방문한 노드를 추가하는데 초기화로 시작노드 destination을 넣는다
4. queue.shift하여 시작노드의 값을 구하고, 2번에서 구한 graph에서 시작노드와 연결된 next를 구한다
5. 시작노드에서 next 까지 최소비용을 구한다 
   1. 누적비용 = 시작노드의 비용 + 1
   2. 누적비용 < distance[next] 이면 distance[next] 즉 next노드까지 최소비용을 갱신한다.
6. next노드를 queue에 넣는다
7. 4번~6번의 과정을 모든 노드를 방문할 때까지, 즉 queue.length === 0 일 때까지 반복한다
8. 매 source까지의 최단비용을 distance에서 구하는데 Infinity이면 즉 비용조차 없다면 -1을 그 외는 distance[source]를 반환한다.

function solution(n, roads, sources, destination) {
    // 그래프생성
    const graph = {};
    roads.forEach(([to, from]) => {
        if (!(to in graph)) {
            graph[to] = [];
        }
        if (!(from in graph)) {
            graph[from] = [];
        }
        graph[to].push(from);
        graph[from].push(to);
    })
    // weightArr, queue 초기화
    const weightArr = Array.from({length: n+1}, () => Infinity);
    weightArr[destination] = 0;
    const queue = [];
    queue.push(destination);
    
    while(queue.length) {
        const curr = queue.shift();
        
        graph[curr].forEach((nextNode) => {
            const acc = weightArr[curr] + 1;
            if (weightArr[nextNode] > acc) {
                weightArr[nextNode] = acc;
                queue.push(nextNode);
            }
        })
    }
    return sources.map(source => weightArr[source] === Infinity ? -1 : weightArr[source])
}