2021 - 합승 택시 요금

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

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

[ 문제풀이 ]

4번 문제치고 굉장히 간단한 문제이다. 그래프에서 특정 지점에서 특정 지점까지의 최단 거리를 구하는 문제이기 때문에 다익스트라나 플로이드 워셜 알고리즘을 사용하면 쉽게 해결할 수 있다.

​나는 플로이드 워셜 알고리즘을 사용하여 해결하였다. 다익스트라 알고리즘보다 플로이드 워셜 알고리즘이 구현하기 훨씬 간단하기 때문이다. n이 최대 200밖에 안되기 때문에 효율성도 문제없이 통과하였다.

​물론 다익스트라 알고리즘을 3번 돌려서 S, A, B에서 갈 수 있는 모든 지점의 최단 거리를 구해주는 방법이 더 효율적이다.

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int[][] dist = new int[n + 1][n + 1];
        
        //Floyd-Warshall
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (i == j) continue;
                dist[i][j] = 20000001; //100000 x 200 + 1
            }
        }
        
        for (int[] fare : fares) {
           dist[fare[0]][fare[1]] = fare[2];
           dist[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 (dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        int answer = 20000001;
        
        for (int i = 1; i <= n; ++i) {
            //dist[s][i] : s지점에서 i지점까지 함께 이동(A, B)
            //dist[i][a] : i지점에서 a지점까지 이동(A)
            //dist[i][b] : i지점에서 b지점까지 이동(B)
            answer = Math.min(answer, dist[s][i] + dist[i][a] + dist[i][b]);
        }
        
        return answer;
    }
}