[프로그래머스] 배달 - javascript

📖 문제링크

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

문제 설명

1부터 N개까지 있는 마을이 있다.
각 마을은 양방향으로 통행할 수 있는 도로가 있다.
서로 다른 마을로 이동할 때는 도로를 지나야하는데 K 시간 이하로 배달이 가능한 마을만 가려고 한다.
배달이 가능한 마을의 수를 return 하여라

📃 조건

• 마을의 개수 N은 1 이상 50 이하의 자연수
• road의 길이(도로 정보의 개수)는 1 이상 2,000 이하
• road는 길이가 3인 배열이며, 순서대로 (a, b, c)
• a, b는 두 마을의 번호, c는 도로를 지나는데 걸리는 시간

👨‍💻 문제풀이

필자가 푼 문제풀이

function solution(N, road, K) {
    const roads = Array.from({ length: N + 1 }, () => []);
    const route = Array.from({ length: N + 1 }, () => Infinity);
    const rocate = [];

    road.map((x) => {
        roads[x[0]].push({
            to: x[1],
            cost: x[2],
        });
        roads[x[1]].push({
            to: x[0],
            cost: x[2],
        });
    });
    
    route[1] = 0;
    rocate.push({to: 1, cost: 0});
    
    while (rocate.length !== 0) {
         rocate.sort((a, b) => a.cost - b.cost);
        
        
        const { to, cost } = rocate.pop();
        roads[to].forEach((nextNode) => {
            if (route[nextNode.to] > route[to] + nextNode.cost) {
                route[nextNode.to] = route[to] + nextNode.cost;
                rocate.push(nextNode);
            }
        });
    }

    return route.filter((x) => x <= K).length;
}

이 문제는 다익스트라 알고리즘을 써야하는 문제였다.
왜냐하면 최소 배달 가능 거리를 알아야하기 때문이다.

그래서 heapq을 많이 사용했는데 js같은 경우 heapq를 사용하기 애매하기 때문에 배열안에 가는 곳과 비용의 값이 들어있는 오브젝트를 사용하였다.

그 다음 비용을 나타내는 배열을 만들고 거리를 알 수 없는 곳은 Infinity값으로 채워주었다.

그 다음 최소 거리로 계속 업데이트하면서 최선의 비용을 구하였다.

사실 이 풀이는 다른 사람들의 풀이를 보면서 풀게 되었다.
이 문제를 풀 때 다익스트라 알고리즘을 알지 못했기 때문이다...

다른 사람들의 풀이를 보고 그 다음 혼자 푼 풀이긴 하지만 다음 번에 다익스트라 알고리즘을 이용하는 코딩테스트를 한 번 풀어봐야겠다.

2022.02.01