프로그래머스 합승 택시 요금 (JAVA)

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

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

 

저는 해당 문제를 플루이드-워샬을 통해서 해결하였습니다. 플루이드-워샬을 통해 각각의 지점에서 다른 지점까지의 최단거리를 구하였습니다.

이를 통해 저는 중간 지점을 거쳐서 가는 요금을 확인하였습니다.

 

import java.util.*;
class Solution {
    static void cal(int[][] map, int n){
        for(int k = 1 ; k <= n ; k++){
            for(int i = 1 ; i <= n ; i++){
                for(int j = 1 ; j <= n ; j++){
                    if( i == j || i == k || j == k || map[i][k] == 0 || map[k][j] == 0){
                        continue;
                    }
                    if(map[i][j] == 0){
                        map[i][j] = map[i][k] + map[k][j];
                    }else{
                        map[i][j] = Math.min(map[i][k] + map[k][j], map[i][j]);
                    }
                }
            }
        }
    }
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        int[][] map = new int[n+1][n+1];
        for(int[] fare : fares){
            int start = fare[0];
            int end = fare[1];
            int weight = fare[2];
            map[start][end] = weight;
            map[end][start] = weight;
        }
        cal(map, n);
        int result = map[s][a] + map[s][b];
        for(int i = 1; i <= n ; i++){
            if((s != i && map[s][i] == 0) || (a != i && map[i][a] == 0) || 
              (b != i && map[i][b] == 0) ){
                continue;
            }
            result = Math.min(result , map[s][i] + map[i][a] + map[i][b]);
        }
        answer = result;
        return answer;
    }
}