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

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

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

1. 유형

플로이드-와샬, 최단거리 탐색

 

2. 시뮬레이션

노드의 개수 N이 최대 200까지 밖에 되지 않는다.

따라서 3중 for문을 사용해도 시간안에 풀이하는 것이 가능.

구현난이도가 낮은 플로이드 와샬을 사용.

 

3. 코드

class Solution {
    static long map[][];
    public int solution(int n, int s, int a, int b, int[][] fares) {
        map = new long[n+1][n+1];
        int INF = 987654321;
        long answer = INF;
        for(int i=0; i<n+1; i++){
            for(int j=0; j<n+1; j++){
                if(i==j) map[i][j]=0;
                else map[i][j]=INF;
            }
        }
        for(int[] fare: fares){
            map[fare[0]][fare[1]] = fare[2];
            map[fare[1]][fare[0]] = fare[2];
        }
        for(int mid=1; mid<=n; mid++){
            for(int start=1; start<=n; start++){
                for(int end=1; end<=n; end++){
                    if(map[start][mid]+map[mid][end] < map[start][end]){
                        map[start][end] = map[start][mid]+map[mid][end];
                    }
                }
            }
        }
        for(int i=1; i<n+1; i++){
            answer = Math.min(map[s][i] + map[i][a] + map[i][b], answer);
        }
        return (int)answer;
    }
}

4. 느낀점

플로이드 와샬에 대해 알 수 있었음.