[JAVA/플로이드 와샬] 프로그래머스 합승 택시 요금

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/72413?language=java 

프로그래머스

 

2. 풀이

• 합승 택시 요금 문제를 (시작점 - 중간점) + (중간점 - A) + (중간점 - B)까지의 비용 합의 최솟값을 구하는 것이라고 정리할 수 있다.
• 따라서, 플로이드 와샬을 이용해 모든 점에서 모든 점 간의 최소 비용을 구하고, 중간점을 거쳤을 때 비용이 최소가 되는 경우를 구한다.
  • 중간점을 거쳤을 때의 비용이 최소가 되는 경우를 구하기 위해서는 
  • min 값을 중간점을 거치지 않은 경우로 초기 설정 해놓고
  • min 값과 (시작점 - 중간점) + (중간점 - A) + (중간점 - B)까지의 값을 비교하여 최솟값을 구한다.

 

3. 코드

import java.util.*;

class Solution {
    
    private static int INF = 100000001;
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int[][] minDis = new int[n+1][n+1]; // a서 b까지의 최소 비용
        for(int i = 0; i <= n; i++){
            Arrays.fill(minDis[i], INF);
            minDis[i][i] = 0;
        }
        
        for(int[] fare : fares){
            minDis[fare[0]][fare[1]] = fare[2];
            minDis[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++){
                    if(minDis[i][k] + minDis[k][j] < minDis[i][j]){
                        minDis[i][j] = minDis[i][k] + minDis[k][j];
                    }
                }
            }
        }
        
        // 시작점서 k, k서 a, k서 b의 거리합의 최솟값 구하기
        int min = minDis[s][a] + minDis[s][b];
        for(int k = 1; k <= n; k++){
            min = Math.min(min, minDis[s][k] + minDis[k][a] + minDis[k][b]);
        }
        
        return min;
    }
}