프로그래머스 Level 2 - 배달
📌 문제 설명
![](https://velog.velcdn.com/images%2Ftnehd1998%2Fpost%2Ff98e2b79-fbaa-4a31-82c8-04566dbdfb7a%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-02-05%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%209.29.11.png)
![](https://velog.velcdn.com/images%2Ftnehd1998%2Fpost%2Fd82331be-86e0-4c13-a0ff-94d394a119aa%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-02-05%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%209.29.24.png)
![](https://velog.velcdn.com/images%2Ftnehd1998%2Fpost%2F5e2ac559-f6e9-4b2a-831b-549b0584ac73%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-02-05%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%209.29.35.png)
📌 생각한 풀이 방법 (다익스트라 알고리즘)
- 연결되어 있는 경로를 모두 lines배열에 저장한다.
- 모든 경로를 탐색하는데 기존에 경로의 값보다 우회하는 값이 더 작으면 해당 값을 저장함
- 경로의 제한인 K보다 cost가 작은 경로의 수를 반환을 함
📌 풀이
function solution(N, road, K) {
const arr = Array(N + 1).fill(Number.MAX_SAFE_INTEGER);
const lines = Array.from(Array(N + 1), () => []);
road.forEach((value) => {
let [a, b, c] = value;
lines[a].push({ to: b, cost: c });
lines[b].push({ to: a, cost: c });
});
let queue = [{ to: 1, cost: 0 }];
arr[1] = 0;
while (queue.length) {
let { to } = queue.pop();
lines[to].forEach((next) => {
if (arr[next.to] > arr[to] + next.cost) {
arr[next.to] = arr[to] + next.cost;
queue.push(next);
}
});
}
return arr.filter((item) => item <= K).length;
}