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

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

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

 

2021 카카오 블라인드에서 출제된 문제이자, 프로그래머스 기준 레벨 3 문제다.

이 문제는 플로이드 와샬 알고리즘을 통해서 해결할 수 있다.

다익스트라 알고리즘은 하나의 정점으로 부터 다른 정점으로의 최단 거리를 구하는 알고리즘이면,

플로이드 와샬 알고리즘은 모든 정점으로부터 모든 정점으로의 최단 거리를 모두 구하는 알고리즘이라고 할 수 있다.

 

다만, 플로이드 와샬 알고리즘은 3중 루프는 사용해야 되기 때문에 알고리즘 효율성 측면에서는 좋다고 보기는 어려우나, 정점의 개수가 많지 않은 경우에 활용하면 좋은 알고리즘이라고 생각한다.

 

문제 유의 사항으로 2차원 배열 초기화를 할 때, 같은 정점끼리는 0 으로 설정하고, 초반에 연결되어 않으면 초기값을 아래와 같이 설정하는 것이 좋다.

• edge 초기값 = 최대 정점 개수 * 최대 비용 값
• 문제에서는 최대 정점 개수 200, 최대 비용 100000 으로 설정해서 20000001 로 설정하도록 한다.

 

예제 코드는 아래와 같다.

class Solution {
    static int MAX_CHARGE = 20000001;

    public static int solution(int n, int s, int a, int b, int[][] fares) {

        int[][] board = new int[n+1][n+1];
        int[][] min_board = new int[n+1][n+1];
        int answer = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) min_board[i][j] = 0;
                else min_board[i][j] = MAX_CHARGE;
            }
        }
        for (int i = 0; i < fares.length; i++) {
            int source = fares[i][0];
            int dest = fares[i][1];
            int charge = fares[i][2];
            min_board[source][dest] = charge;
            min_board[dest][source] = charge;
        }
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (min_board[i][j] > min_board[i][k] + min_board[k][j]) {
                        min_board[i][j] = min_board[i][k] + min_board[k][j];
                    }
                }
            }
        }


        for (int k = 1; k <= n; k++) {
            int total = min_board[s][k] + min_board[k][a] + min_board[k][b];
            answer = total < answer ? total : answer;
        }
        return answer;
    }
}