강의로 돌아가기
JS 풀이 (!정답코드 포함)
해당문제는 최단거리 알고리즘 풀이를 사용해야한다.
처음 떠오른 알고리즘은 다익스트라 알고리즘 이다.
단순히 시작점 s 에서 a지점과 b지점까지 각각의 최단거리를 구하는 문제였다면 다익스트라 알고리즘을 사용하는게 맞다.
하지만 주어진 문제 조건에서는 같은 택시로 이동하다가 특정 경유지에서 다른 택시를 나누어서 타 이동하는 경우의 수도 전체 경우에 포함이 된다.
따라서 모든 정점에서 모든 정점까지 최단거리를 계산하는 플로이드-워셜 알고리즘으로 해결해야한다.
플로이드-워셜 알고리즘의 시간복잡도는 O( N3 ) 으로 좋지 않기때문에 주어진 n의 최대 경우의 수도 확인해주었다.
해당문제에서는 n의 최대값이 200으로 해당 알고리즘을 사용해도 무리없을 것으로 판단했다.
*알고리즘에 대한 코드는 해당 포스팅을 참고했다. 플로이드-워셜 알고리즘(JS)
function solution(n, s, a, b, fares) {
const INF = Infinity;
const graph = Array(n).fill().map(() => Array(n).fill(INF));
fares.forEach(([x, y, cost]) => {
graph[x - 1][y - 1] = cost;
graph[y - 1][x - 1] = cost;
})
for(let i = 0; i < n; i++) graph[i][i] = 0;
const floydWarshall = (dist) => {
const len = dist.length;
for(let i = 0; i < len; i++) {
for(let j = 0; j < len; j++) {
for(let k = 0; k < len; k++) {
dist[j][k] = Math.min(dist[j][k], dist[j][i] + dist[i][k]);
}
}
}
}
floydWarshall(graph);
let min = INF;
// waypoint = s-1 인 경우는 경유지 없이 출발점에서 각각 따로 이동하는 경우
for(let waypoint = 0; waypoint < n; waypoint++) {
min = Math.min(min, graph[s - 1][waypoint] + graph[waypoint][a - 1] + graph[waypoint][b - 1]);
}
return min;
}
-
이걸 어떻게 푸나 막막했었는데 덕분에 뭘 공부해야 하는지 알았네요. 감사히 보고 갑니다!
CGJI58―2023.09.05 13:03
-
감사합니다
SungilRyuu―2024.08.30 11:48
