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

 

문제

프로그래머스

 

알고리즘

플로이드 워셜

 

풀이

예제 그림을 보면 정점이 6개이므로 같이 택시를 탈 수 있는 경우의 수도 다음과 같이 6가지이다.

 

(cost(i, j) = 정점 i에서 정점 j까지 드는 최소 비용)

1번 정점까지 합승 = cost(4, 1) + cost(1, 6) + cost(1, 2)

2번 정점까지 합승 = cost(4, 2) + cost(2, 6) + cost(2, 2)

3번 정점까지 합승 = cost(4, 3) + cost(3, 6) + cost(3, 2)

4번 정점까지 합승 = cost(4, 4) + cost(4, 6) + cost(4, 2) = 합승하지 않은 경우

5번 정점까지 합승 = cost(4, 5) + cost(5, 6) + cost(5, 2) 

6번 정점까지 합승 = cost(4, 6) + cost(6, 6) + cost(6, 2)

 

따라서

1. 시작 정점(4번)부터 다른 정점으로 가는 최소 비용

2. A번 정점(6번)부터 다른 정점으로 가는 최소 비용

3. B번 정점(2번)부터 다른 정점으로 가는 최소 비용

을 모두 알고 있어야하므로

세 정점을 대상으로 다익스트라 알고리즘을 사용하거나 플로이드 워셜 알고리즘을 사용해야한다.

(n이 최대 200이므로 n³ = 800만)

따라서 플로이드 워셜 알고리즘을 사용하여 모든 정점으로부터 다른 모든 정점으로 가는 최소 비용을 구하고

1번 정점부터 n번 정점까지 합승했을 때까지 비용 중 최소 비용을 구한다.

 

코드

import java.util.*;

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        int INF = 87_654_321;
        int[][] dist = new int[n+1][n+1];
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(i != j) dist[i][j] = INF;
        
        for(int[] fare : fares) {
            dist[fare[0]][fare[1]] = fare[2];
            dist[fare[1]][fare[0]] = fare[2];
        }
        
        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        
        int min = Integer.MAX_VALUE;
        for(int i=1; i<=n; i++) {
            min = Math.min(min, dist[s][i] + dist[i][a] + dist[i][b]);
        }
        return min;
    }
    
}