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

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

 

소요시간 : 34분

 

플로이드와샬 문제였다

이 문제가 플로이드와샬 문제라는 것을 알고 풀었으니 할 수 있었지

그게 아니었다면 못 풀었을 듯...

플로이드와샬 개념을 알고 있다면 쉽다..

 

그래프를 인접행렬에 입력하고

모든 출발지와 경유지와 도착지에 대해서 최소값을 갱신 후

 

i 가 1 ~ n 에 대해서

s -> i , i -> a, i -> b 를 더한 값이 최소인 값을 반환하면 된다.

class Solution {
    static final int INFINITY = Integer.MAX_VALUE;

    public int solution(int n, int s, int a, int b, int[][] fares) {
    	int[][] adjMatrix = new int[n+1][n+1];
    	for (int i = 1; i <= n; i++) {
    		for (int j = 1; j <= n; j++) {
    			if(i == j) adjMatrix[i][j] = 0;
    			else adjMatrix[i][j] = INFINITY;
    		}
    	}
    	
    	for (int i = 0; i < fares.length; i++) {
    		adjMatrix[fares[i][0]][fares[i][1]] = fares[i][2];
    		adjMatrix[fares[i][1]][fares[i][0]] = fares[i][2];
    	}

    	for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				for (int k = 1; k <= n; k++) {
					if(i == j || i == k || j == k) continue;
					if(adjMatrix[j][i] == INFINITY || adjMatrix[i][k] == INFINITY) continue;
					adjMatrix[j][k] = Math.min(adjMatrix[j][k], adjMatrix[j][i] + adjMatrix[i][k]);
				}
			}
		}
    	
		int answer = INFINITY;
    	for (int i = 1; i <= n; i++) {
    		answer = Math.min(answer, adjMatrix[s][i] + adjMatrix[i][a] + adjMatrix[i][b]);
    	}
    	
        return answer;
    }
}