[프로그래머스][level3] 합승 택시 요금 (Kotlin)

https://programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

 

[난이도] level3
[유형] 플로이드 워셜

[풀이]

s에서 어떤 점 k(1~n)까지 같이 타고 갔다고 가정했을 때 요금의 최솟값은
s~k까지의 최단거리 + k~a의 최단거리 + k~b의 최단거리 입니다.
k를 1에서 n까지 바꿔보면서 최단거리를 모두 구해봤을 때의 최솟값이 정답입니다.
모든 점 (i,j)간의 최단거리를 구해야 하므로 플로이드 워셜 알고리즘을 이용하였습니다.

 

import java.lang.Integer.min
import java.util.*
const val inf = 20000001
var cost = Array(201){IntArray(201){inf} }
class Solution {
    fun solution(n: Int, s: Int, a: Int, b: Int, fares: Array<IntArray>): Int {
        var answer = inf
        for(v in fares){
            cost[v[0]][v[1]]=v[2]
            cost[v[1]][v[0]]=v[2]
        }
        for(i in 1..n) cost[i][i]=0

        for(k in 1..n){
            for(i in 1..n){
                for(j in 1..n){
                    if(cost[i][j] > cost[i][k]+cost[k][j]){
                        cost[i][j] = cost[i][k]+cost[k][j]
                        cost[j][i] = cost[i][j]
                    }
                }
            }
        }
        for(i in 1..n) answer = min(answer, cost[i][s] + cost[i][a] + cost[i][b])

        return answer
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/합승_택시_요금.cpp