프로그래머스 배달 JavaScript
2023년 1월 25일
문제 풀이
그래프 탐색 문제, N개의 마을 중 1번 마을에서 k 시간 이하로 이동이 가능한 마을의 수를 찾는 문제다.
townTimes: 1번 마을에서 그 마을까지의 가는 시간을 저장하는 배열towns: 마을을 연결하고 있는 각 도로의 정보를 저장하는 배열, 같은 마을을 연결하는 도로가 있을 수 있지만 이 문제에서는 도로 이동시간의 최솟값만 필요하기에 최솟값만 갱신한다.
- 마을 간 연결된 길이 있을 때
- 현재 시간+이동 시간이 저장된
townTimes의 값 보다 작을 때 - 현재 시간+이동 시간이 K 보다 작을 때
를 모두 만족하면 townTimes을 갱신하고 que에 push 한다.
마지막으로 townTimes 값이 K 보다 작거나 같을 때 시간 안에 이동 가능한 마을이므로 ++ 해준다.
solution.js
function solution(N, road, K) {
let answer = 0;
const townTimes = new Array(N+1).fill(K+1);
const towns = new Array(N+1).fill(0).map(() => new Array(N+1).fill(10001));
const que = [];
road.forEach(element => {
const [a, b, c] = element;
towns[a][b] = towns[a][b] > c ? c : towns[a][b];
towns[b][a] = towns[b][a] > c ? c : towns[b][a];
});
que.push(1);
townTimes[1] = 0;
while (que.length > 0) {
const town = que.shift();
for (let i = 1; i <= N; i++) {
const moveTime = towns[town][i] + townTimes[town];
if (towns[town][i] !== 10001 && moveTime < townTimes[i] && moveTime <= K) {
que.push(i);
townTimes[i] = moveTime;
}
}
}
for (let i = 1; i <= N; i++) {
if (townTimes[i] <= K) {
answer++;
}
}
return answer;
}