(프로그래머스 JS)배달

https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

다익스트라를 이용한 문제풀이.

 

우선 road에 담겨있는 정보(시작 마을, 도착 마을, 비용)를 담을 수 있는 graph를 선언.

dist는 각 마을까지 갈 수 있는 최소 비용을 저장하는 배열이다.

queue는 다익스트라를 진행할 때 사용하는 배열.

 

for문으로 road에 담겨져 있는 정보를 graph에 담는다.

start 번호로 시작하는 마을에서 target까지 cost 비용이 걸린다는 뜻이다.

==> graph[start][target][cost]

 

이제 시작 마을인 1번과 시작 비용인 0을 queue에 담아 시작한다.

또한, 1번 마을까지의 비용을 0으로 설정한 후 진행.

 

다익스트라로 최소 비용을 갱신한다.

현재 담겨져 있는 마을 번호와 비용을 queue.shift()를 통해 꺼낸다.

current 번호에서 갈 수 있는 정보는 graph에 담겨져 있으므로 해당 길이만큼 for문 실행.

current에서 갈 수 있는 마을 번호를 next, 가는 비용을 nextCost라고 정한다.

 

이미 저장되어 있는 dist[next]와 현재까지의 비용 + nextCost 중 더 작은 값을

dist[next]에 갱신하고, 큐에 다음 마을 정보를 저장해 다익스트라를 계속 진행한다.

 

마지막에는 dist를 for문으로 돌아, K 비용만큼 갈 수 있는 마을의 수를 리턴하면 된다.

function solution(N, road, 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 < road.length; i++){
        const start = road[i][0];
        const target = road[i][1];
        const cost = road[i][2];
        
        graph[start].push([target, cost]);
        graph[target].push([start, cost]);
    }
    
    queue.push([1, 0]);
    dist[1] = 0;
    
    while(queue.length){
        const [current, cost] = queue.shift();
        
        for(let i = 0; i < graph[current].length; i++){
            const next = graph[current][i][0];
            const nextCost = graph[current][i][1];
            
            if(dist[next] > dist[current] + nextCost){
                dist[next] = dist[current] + nextCost;
                queue.push([next, nextCost]);
            }
        }
    }
    
    
    for(let i = 1; i <= N; i++){
        answer += dist[i] <= K ? 1 : 0;
    }
    
    return answer;
}