배달

배달 (프로그래머스)

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

문제 설명

N개의 마을로 이루어진 나라가 있습니다.

이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다.

각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데,

서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다.

도로를 지날 때 걸리는 시간은 도로별로 다릅니다.

현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다.

각 마을로부터 음식 주문을 받으려고 하는데,

N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다.

풀이

다익스트라 알고리즘을 사용하여 풀었습니다

거리에 따른 최소 비용을 저장한 배열을 생성하고(초기값을 무한대로)

출발지점에서 도착지점까지 최소비용을 저장할 배열을 선언합니다

경로를 탐색하며 거리에 따른 최소 비용 배열에 저장한 값보다 낮으면 정보를 업데트하며 탐색합니다

 

function solution(N, road, K) {
    const costByDist = Array(N + 1).fill(Infinity);
    const moveCost = Array.from(Array(N + 1), () => []);

    road.forEach((value) => {
        let [a, b, c] = value;
        moveCost[a].push({ to: b, cost: c });
        moveCost[b].push({ to: a, cost: c });
    });

    let queue = [{ to: 1, cost: 0 }];
    costByDist[1] = 0;

    while (queue.length) {
        let { to } = queue.pop();
        moveCost[to].forEach((next) => {
            if (costByDist[next.to] > costByDist[to] + next.cost) {
                costByDist[next.to] = costByDist[to] + next.cost;
                queue.push(next);
            }
        });
    }
    return costByDist.filter((item) => item <= K).length;
}