[programmers] 합승 택시 요금

문제 풀이 : 2021.04.29

문제 풀이

시작점부터 도착지점까지의 최소 비용에 관한 문제이고 다익스트라와 플로이드 와샬 알고리즘을 사용할 수 있다. '합승을 하는 구간' -> '거쳐가는 노드'로 해석할 수 있으므로 플로이드 와샬 알고리즘을 사용하면 된다.

코드

class Solution {
    static int[][] f;
    int INF = 20000001;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 2147483647;
        f = new int[n][n];
        for(int i = 0;i<n;i++)
            for(int j = 0;j<n;j++){
                if(i==j)f[i][j] =0;
                else f[i][j] = INF;
            }
        for(int i = 0 ;i<fares.length;i++){
            f[fares[i][0]-1][fares[i][1]-1] = fares[i][2];
            f[fares[i][1]-1][fares[i][0]-1] = fares[i][2];
        }
        floyd(n);
        for(int i = 0;i<n;i++)
            answer = Math.min(answer, f[s-1][i]+f[i][a-1]+f[i][b-1]);    
        return answer;
    }
    
    static void floyd(int n){
        for(int k=0; k<n; k++){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(f[i][j]>f[i][k]+f[k][j])
                        f[i][j] = f[i][k]+f[k][j];
                }
            }
        }
    }
}

문제 출처 : 링크
GitHub : 링크