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

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

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

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

풀이

방향성이 없는 연결 그래프에서 최단 경로를 구해야 하는 문제였다. 처음에는 MST알고리즘인 prim알고리즘으로 풀려고 했으나 prim은 도착 노드가 정해진 것이 아니라 그래프의 최단 경로를 반환하기 때문에 적합하지 않았다.

 

풀고보니 그냥 플로이드-와샬 알고리즘만 쓰면 정답이었다. 결국에는 모든 정점에서 모든 정점으로 가는 거리를 계산해 준 다음 그 중에 조건에 맞는 최단거리를 뽑아내면 되기 때문이다. 이 때문에 다익스트라 알고리즘을 사용해서도 풀 수 있을 듯 하다. 다익스트라는 한 정점에서 모든 정점으로의 최단 거리를 계산하기 때문에 시작 정점을 반복문을 통해 바꾸어 주면서 계산하면 될 것 같다. 다익스트라로 풀면 시간 복잡도와 공간 복잡도 모두 플로이드-와샬 알고리즘을 사용했을 때 보다 효율적일 것 이다.

 

프로그래머스에서 플로이드-와샬 알고리즘을 처음 접했는데(알고리즘 수업시간에도 교수님이 별로 중요하지 않다고 했던 알고리즘이었다.) 카카오 문제에도 나오는걸 보면 프로그래머스에서 주관하는 코딩테스트에서는 종종 나올일이 있을수도 있겠다...

 

플로이드-와샬 알고리즘에 대해 간략하게 설명하자면, 아주 간단하다.

현재 node[i][j]로 가는 비용보다 더 작은 값으로 node[i][j]로 갈 수 있는 경로를 발견한다면 그 값으로 갱신해 주면 된다.

즉, node[i][j]보다 node[i][k] + node[k][j] (k를 경유해서 가는 방법)이 더 작은 값이라면 갱신해준다.

이런 방법으로 모든 노드에서 모든 노드로 가는 최단 경로를 알 수 있다. 시간 복잡도는 O(n^3)으로 다소 오래걸리는 편이다.

 

코드

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int[][] node = new int[n + 1][n + 1];
        for(int i = 1; i < n + 1; i++) {
            for(int j = 1; j < n + 1; j++) {
                node[i][j] = 20000001; //200 * 100000 + 1
            }
            node[i][i] = 0;
        }
        
        for(int i = 0; i < fares.length; i++) {
            node[fares[i][0]][fares[i][1]] = fares[i][2];
            node[fares[i][1]][fares[i][0]] = fares[i][2];
        }
        
        for(int k = 1; k < n + 1; k++) {
            for(int i = 1; i < n + 1; i++) {
                for(int j = 1; j < n + 1; j++) {
                    if(node[i][j] > node[i][k] + node[k][j]) {
                        node[i][j] = node[i][k] + node[k][j];
                    }
                }
            }
        }
        
        int min = Integer.MAX_VALUE;
        for(int i = 1; i < n + 1; i++) {
            min = Math.min(min, node[s][i] + node[i][a] + node[i][b]);
        }
        return min;
    }
}