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

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

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

 

참고 링크 : https://moonsbeen.tistory.com/51

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

 

 - 풀이

 - 각 지점(a,b,s) 에서의 최단 거리를 구하는 문제

 - 각 지점의 최단거리를 구한 합이 답이 된다.

 - 따라서 모든 정점까지의 최단 거리를 구하는 플로이드-워셜 알고리즘을 이용한다.

 - 답을 보고 품.

 

- 후기 & 피드백

 - 혼자서 초기화 후 한번 더 진행.

 

 

class Solution {
    private int MAX_VAL = 20000001;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = MAX_VAL;
        int[][] d = new int[n+1][n+1];
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                d[i][j] = MAX_VAL;
            }
            d[i][i] = 0;
        }
        
        for(int i=0; i<fares.length; i++) {
            d[fares[i][0]][fares[i][1]] = fares[i][2];
            d[fares[i][1]][fares[i][0]] = fares[i][2];
        }
        
        for(int k=1; k<=n ; k++) {
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=n; j++) {
                    if(d[i][j] > d[i][k] + d[k][j]) {
                        d[i][j] = d[i][k] + d[k][j];
                    }
                }
            }
        }
        
        for(int i=1; i<=n; i++) {
            answer = Math.min(answer, d[s][i] + d[i][a] + d[i][b]);
        }
        
        return answer;
    }
}