https://school.programmers.co.kr/learn/courses/30/lessons/12978
처음에 테스트케이스 2개만 성공해서 힌트를 봤는데 플로이드-워셜 알고리즘을 쓰면 된다고 했다.
플로이드-워셜 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다.
위의 그림을 보면 1에서 4로 바로 갈 수 있는 경로가 없지만 중간 노드 2와 5를 거친다면 4로 갈 수 있다.
2를 거쳐가는 경우는 거리가 7이고, 5를 거쳐가는 경우 거리가 -1이기 때문에 1에서 4로 가는 최단 거리는 -1이 된다.
이를 구하는 방법은
NxN 배열에(chart) 노드 start에서 end에서 직접적으로 연결되어 있다면 그 노드의 가중치만큼, 그렇지 않다면 무한(INF)으로 초기화 한다.
최단 거리를 구하기 위해 start와 end사이의 모든 노드 mid에 대해 현재 chart[start][end]에 저장되어 있는 값과 chart[start][mid] + chart[mid][end] 값을 비교했을 때 더 작은 값(최단 거리)으로 업데이트 한다.
function floid(chart){
for (let mid = 0; mid < chart.length; mid++) {
for (let start = 0; start < chart.length; start++) {
for (let end = 0; end < chart.length; end++) {
chart[start][end] = Math.min(chart[start][end], chart[start][mid] + chart[mid][end]);
}
}
}
return chart;
}
function solution(N, road, K) {
var graph = new Array(N).fill().map(()=> new Array(N).fill(Infinity));
// NxN배열 graph에 Infinity를 넣어서 초기화
var answer = 0;
for(let i = 0; i < N; i++){
graph[i][i] = 0;
}
// graph배열에 자기 자신으로 가는 경로를 0으로 넣어줌
for(let i = 0; i < road.length; i++){
graph[road[i][0]-1][road[i][1]-1] = Math.min(graph[road[i][0]-1][road[i][1]-1],road[i][2]);
graph[road[i][1]-1][road[i][0]-1] = Math.min(graph[road[i][0]-1][road[i][1]-1],road[i][2]);
}
// graph배열에 주어진 경로중 최단 거리를 넣어줌 (3,5,3, 3,5,2 가 있을 때 3->5는 2를 넣어줌)
function floid(chart){
for (let mid = 0; mid < chart.length; mid++) {
for (let start = 0; start < chart.length; start++) {
for (let end = 0; end < chart.length; end++) {
chart[start][end] = Math.min(chart[start][end], chart[start][mid] + chart[mid][end])
}
}
}
return chart;
}
graph = floid(graph);
for(let i = 0; i < N; i++){
if(graph[0][i] <= K){ // 1번에서 가는 경로이기 때문에 graph[0]의 원소 중 K이하의 원소의 개수를 세어줌
answer++;
}
}
return answer;
}
function solution(N, road, K) {
const totalDist = new Array(N+1).fill(Infinity);
const adj = Array.from({length: N+1}, () => []);
// 인덱스가 0부터 시작이라서 N+1
road.forEach(([a,b,c]) => {
adj[a].push({to: b, dist: c})
adj[b].push({to: a, dist: c})
})
const queue = [{to: 1, dist: 0}];
totalDist[1] = 0;
while(queue.length) {
let {to, dist} = queue.pop();
adj[to].forEach((step) => {
if (totalDist[step.to] > totalDist[to] + step.dist) {
totalDist[step.to] = totalDist[to] + step.dist;
queue.push(step);
}
})
}
return totalDist.filter((dist) => dist <= K).length;
}
나도 객체랑 forEach 간지나게 쓰고 싶다...