N
(프로그래머스 JS)배달 본문
https://programmers.co.kr/learn/courses/30/lessons/12978
코딩테스트 연습 - 배달
5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4
programmers.co.kr
다익스트라를 이용한 문제풀이.
우선 road에 담겨있는 정보(시작 마을, 도착 마을, 비용)를 담을 수 있는 graph를 선언.
dist는 각 마을까지 갈 수 있는 최소 비용을 저장하는 배열이다.
queue는 다익스트라를 진행할 때 사용하는 배열.
for문으로 road에 담겨져 있는 정보를 graph에 담는다.
start 번호로 시작하는 마을에서 target까지 cost 비용이 걸린다는 뜻이다.
==> graph[start][target][cost]
이제 시작 마을인 1번과 시작 비용인 0을 queue에 담아 시작한다.
또한, 1번 마을까지의 비용을 0으로 설정한 후 진행.
다익스트라로 최소 비용을 갱신한다.
현재 담겨져 있는 마을 번호와 비용을 queue.shift()를 통해 꺼낸다.
current 번호에서 갈 수 있는 정보는 graph에 담겨져 있으므로 해당 길이만큼 for문 실행.
current에서 갈 수 있는 마을 번호를 next, 가는 비용을 nextCost라고 정한다.
이미 저장되어 있는 dist[next]와 현재까지의 비용 + nextCost 중 더 작은 값을
dist[next]에 갱신하고, 큐에 다음 마을 정보를 저장해 다익스트라를 계속 진행한다.
마지막에는 dist를 for문으로 돌아, K 비용만큼 갈 수 있는 마을의 수를 리턴하면 된다.
function solution(N, road, K) {
let answer = 0;
const graph = Array.from({length: N + 1}, () => Array());
const dist = Array(N + 1).fill(Infinity);
const queue = [];
for(let i = 0; i < road.length; i++){
const start = road[i][0];
const target = road[i][1];
const cost = road[i][2];
graph[start].push([target, cost]);
graph[target].push([start, cost]);
}
queue.push([1, 0]);
dist[1] = 0;
while(queue.length){
const [current, cost] = queue.shift();
for(let i = 0; i < graph[current].length; i++){
const next = graph[current][i][0];
const nextCost = graph[current][i][1];
if(dist[next] > dist[current] + nextCost){
dist[next] = dist[current] + nextCost;
queue.push([next, nextCost]);
}
}
}
for(let i = 1; i <= N; i++){
answer += dist[i] <= K ? 1 : 0;
}
return answer;
}
'프로그래머스 알고리즘 > 2단계' 카테고리의 다른 글
(프로그래머스 JS)쿼드압축 후 개수 세기 (0) | 2022.03.30 |
---|---|
(프로그래머스 JS)방문 길이 (0) | 2022.03.14 |
(프로그래머스 c++)행렬 테두리 회전하기 (0) | 2021.06.24 |
(프로그래머스 JS)올바른 괄호 (0) | 2021.06.23 |
(프로그래머스 JS)예상 대진표 (0) | 2021.06.15 |