[JS] 2Level / Summer/Winter Coding(~2018) / 배달

문제 설명

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

프로그래머스

 

문제 풀이 방법

이 문제는 특정 노드에서 다른 모든 노드로 가는 최단 경로를 구할 수 있는 다익스트라 알고리즘을 이용하는 문제이다.(다스트라 알고리즘은 추후 정리할 것이다)

 

1번(특정 노드)에서 출발해 각 번호까지의 코스트를 적립해 주어진 제한 코스트를 넘지 않는 번호의 갯수를 구하는 문제인데, 이 문제에서 BFS와 우선순위 큐를 이용해 다익스트라 알고리즘을 구현했다.

순수 BFS는 가중치가 없는 그래프를 이용해 방문하지 않은 노드를 탐색하며 진행하기에,
가중치가 있는 해당 문제에서는 순수 BFS만 사용하지 않았다.

 

 

참고한 코드

const solution = (N, road, K) => {
    let answer = Array(N + 1).fill(Infinity);
    let temp = Array.from({length: N + 1}, () => []);
    
    answer[1] = 0;
    
    road.forEach((e) => {
        temp[e[0]].push([e[1], e[2]]);
        temp[e[1]].push([e[0], e[2]]);
    })
    let que = [[1, 0]];
    
    while(que.length){
        let [to, time] = que.pop();
        temp[to].forEach(e => {
            if(e[1] + answer[to] < answer[e[0]] ){
                answer[e[0]] = e[1] + answer[to];
                que.push(e);
            }
        })
    }
    
    return answer.filter(e => e <= K).length;
}