[다익스트라] 배달

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

프로그래머스

 

문제정리

1번 마을에서 출발 K시간 이하까지의 마을에 배달을 한다. 배달이 되는 마을 갯수는?

1에서 각 마을까지 최단거리 배열을 구하고 그 중 최단거리가 K보다 작은 마을 갯수를 리턴한다

 

첫번째 풀이(성공)

하나의 시작노드에서 다른 노드로 이동, 최단기간 => 다익스트라

 

1. 그래프 생성
2. weightArr, queue 시작점 초기화
3. while queue 순회
    3-1. 이웃노드찾기
    3-2. 이웃노드의 새로운 가중치 계산하기
    3-3. 3-2에서 찾은 새로운 가중치가 기존의 가중치보다 작으면 가중치를 갱신하고, queue에 push한다

 

 

function solution(N, road, K) {
    // 양방향 그래프생성
    const graph = {};
    road.forEach(r => {
        const [from, to, weight] = r;
        if (!(from in graph)) {
            graph[from] = [];
        }
        if (!(to in graph)) {
            graph[to] = [];
        }
        graph[from].push({nextNode: to, nextWeight: weight});
        graph[to].push({nextNode: from, nextWeight: weight});
    })
    const weightArr = Array.from({length: N+1}, () => Infinity); // 각 점마다 최단거리 초기화
    const queue = [];
    queue.push({currNode: 1, currWeight: 0}); // 시작점
    weightArr[1] = 0; // 시작점 방문 표시
    
    while(queue.length) {
        const {currNode, currWeight} = queue.shift();
        // 현재위치의 주변
        graph[currNode].forEach(({nextNode, nextWeight}) => {
            const acc = currWeight + nextWeight;
            // 더 짧은 최단거리를 구하면 갱신
            if (acc < weightArr[nextNode]) {
                // weightArr[nextNode] = Math.min(weightArr[nextNode], acc);
                weightArr[nextNode] = Math.min(acc);
                queue.push({currNode: nextNode, currWeight: acc}); // 다음 노드로 이동
            }
        })
    }
    return weightArr.filter(weight => weight <= K).length;
}