[프로그래머스#JS] 합승 택시 요금
문제
https://programmers.co.kr/learn/courses/30/lessons/72413
해결
- 노드의 최대 길이가 200 이기 때문에 플로이드 와샬 알고리즘이 가능하다.
// 결과
0: [0, 63, 41, 10, 24, 25]
1: [63, 0, 22, 66, 46, 48]
2: [41, 22, 0, 51, 24, 26]
3: [10, 66, 51, 0, 34, 35]
4: [24, 46, 24, 34, 0, 2]
5: [25, 48, 26, 35, 2, 0]
- start 지점(4) 에서 공유 지점 + 공유지점 에서 a + 공유지점 에서 b 까지 길이의 최솟값을 구하면 된다.
answer = Math.min(answer, map[s-1][i] + map[i][a-1] + map[i][b-1]);
코드
function solution(n, s, a, b, fares) {
// 그래프 세팅
let map = Array.from(new Array(n), () => new Array(n).fill(Infinity));
map.forEach((row, idx) => (row[idx] = 0));
fares.forEach((fare) => {
const [from, to, cost] = fare;
map[from - 1][to - 1] = cost;
map[to - 1][from - 1] = cost;
});
// 플로이드 와샬
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
if (map[i][k] === Infinity) continue;
for (let j = 0; j < n; j++) {
if (map[k][j] === Infinity) continue;
map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
}
}
}
let answer = Infinity;
// s - 공유 지점 + 공유 지점 - a + 공유 지점 -b
for (let i = 0; i < n; i++) {
answer = Math.min(answer, map[s-1][i] + map[i][a-1] + map[i][b-1]);
}
return answer;
}
Author And Source
이 문제에 관하여([프로그래머스#JS] 합승 택시 요금), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tunakim/프로그래머스JS-합승-택시-요금저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)