https://school.programmers.co.kr/learn/courses/30/lessons/72413
위와 같은 택시 경로에서 S에서 출발해 특정 위치까지 합승해 이동한 후, 해당 위치에서 A와 B로 각각 이동하는 비용 중 최소 비용을 구하는 문제이다.
출발 위치인 S에서 합승하지 않고 각각 A와 B로 이동하는 것이 최소 경로라면 합승하지 않아도 된다.
제한사항
- 지점 개수 n은 3~200이다.
- s, a, b는 1~n까지의 값으로, 모두 다르다.
- s에서 a와 b로 갈 수 있는 경로가 존재하는 경우만 입력으로 주어진다.
지점 개수가 최대 200개 이고 간선 개수는 최대 (200 * 199) / 2이므로 약 2만개 까지이다.
따라서 위 문제는 다익스트라나 플로이드로도 풀이가 가능하다고 판단하였다.
다익스트라: - 20000 log 200 정도
플로이드: $$O(n^3) - 200 200 200 = 8,000,000 정도
단 위 풀이를 위해서 플로이드는 값을 한 번만 구하면 되고 다익스트라는 여러 번 구해야 하는 점이 있다.
다익스트라를 이용한 풀이
먼저 다익스트라를 이용한 풀이이다.
S부터 특정 경유지로 최단 거리로 이동하고, 그 경유지에서 a와 b로 최단 거리로 이동하며 사용된 비용의 합들 중 최솟값을 구하면 된다.
먼저 S에서 다익스트라를 통해 다른 지점들로 이동하는 최소 비용들을 구한다.
그리고 1부터 n까지 반복하며 경유지(wp)로 설정하고, 해당 경유지(wp)에서 다익스트라를 통해 최소 비용을 구하고 wp~a, wp~b의 비용을 구한다.
그럼 총 비용은 s_dijk[wp] + wp_dijk[a] + wp_dijk[b]이다.
(s_dijk는 s에서의 다익스트라, wp_dijk는 wp에서의 다익스트라)
1~n까지 각 지점을 경유지로 설정해 위 비용값을 구해 최솟값을 출력한다.
class Solution {
fun solution(n: Int, s: Int, a: Int, b: Int, fares: Array<IntArray>): Int {
val links = Array(n + 1){ LinkedList<V>() }
val pq = PriorityQueue<V>{ v1, v2 -> v1.cost - v2.cost }
for(e in fares){
links[e[0]].add(V(e[1], e[2]))
links[e[1]].add(V(e[0], e[2]))
}
fun dijkstra(start: Int): IntArray{
val distances = IntArray(n + 1){ Int.MAX_VALUE }
distances[start] = 0
pq.offer(V(start, 0))
while(pq.isNotEmpty()){
val now = pq.poll()
if(distances[now.n] < now.cost)
continue
for(j in links[now.n]){
val cost = now.cost + j.cost
if(distances[j.n] > cost){
distances[j.n] = cost
pq.offer(V(j.n, cost))
}
}
}
return distances
}
val s_dijk = dijkstra(s)
var minCost = Int.MAX_VALUE
for(i in 1 until s_dijk.size){
val dijk = dijkstra(i)
val cost = s_dijk[i] + dijk[a] + dijk[b]
if(cost < minCost)
minCost = cost
}
return minCost
}
}
data class V(
val n: Int,
val cost: Int = 0
)플로이드를 이용한 풀이
다익스트라를 이용한 풀이와 개념은 동일하다.
플로이드를 통해 비용들을 한꺼번에 구해놓은 뒤 1~n까지 반복하며 경유지(wp)로 설정한 뒤에 S에서 wp로, wp에서 각각 a와 b로 이동하는 비용을 합친 값들 중 최소를 구한다.
비용은 floyd[S][wp] + floyd[wp][a] + floyd[wp][b]이다.
class Solution {
fun solution(n: Int, s: Int, a: Int, b: Int, fares: Array<IntArray>): Int {
val links = Array(n + 1){ IntArray(n + 1){123456789} }
for(e in fares){
links[e[0]][e[1]] = e[2]
links[e[1]][e[0]] = e[2]
}
val floyd = Array(n + 1){ IntArray(n + 1){123456789} }
fun floyd(){
for(i in 1..n){
for(j in 1..n){
floyd[i][j] = links[i][j]
if(i == j) floyd[i][j] = 0
}
}
for(k in 1..n) for(i in 1..n) for(j in 1..n)
floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j])
}
floyd()
var minCost = Int.MAX_VALUE
for(wp in 1..n){
val cost = floyd[s][wp] + floyd[wp][a] + floyd[wp][b]
if(cost < minCost) minCost = cost
}
return minCost
}
}n이 최대 200인 해당 문제에서는 플로이드 알고리즘으로 한 번 구하고 탐색하는 방법이 확실히 빨랐다.
다익스트라는 인 플로이드가 감당할 수 없을 크기의 n이 주어지는 경우에 사용될 수 있을 것 같다.
