[2021 KAKAO BLIND RECRUITMENT] 합승 택시 요금

2021 KAKAO BLIND RECRUITMENT 합승 택시 요금

유형

• 그래프
• 최단거리 탐색 (다익스트라, 플로이드 워셜)

문제 풀이에 대한 감을 잡기 위해, 카카오 공식 문제 해설을 먼저 참고하였다.

문제 풀이
그래프에서 최단 경로를 구하는 “dijkstra 알고리즘”, 또는 “Floyd-Warshal 알고리즘”을 사용하면 풀 수 있는 문제입니다.

이중 플로이드 알고리즘을 사용하여서 문제를 푼다고 가정하면, 다음과 같이 모든 지점 사이의 최저 예상 택시요금을 구할 수 있습니다.

d[i][j] = i번 지점에서 j번 지점까지 갈 때의 최저 예상 택시요금
그 다음, 다음과 같이 루프를 돌면서 최솟값을 찾아주면 됩니다.

문제에서 요구하는 답 = min(d[s][k] + d[k][a] + d[k][b]) (단, k = 1 ~ n)

다익스트라나, 플로이드 워셜 알고리즘에 대한 지식이 필요한 문제였다.

코드

import java.util.Arrays;

class Solution {

    static int[][] dist;
    static final int INF = 20000001;

    //n 지점개수, s 출발지점, a A도착지점, b B도착지점, fares 택시요금
    public int solution(int n, int s, int a, int b, int[][] fares) {
        dist = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }

        for (int i = 0; i < fares.length; i++) {
            dist[fares[i][0]][fares[i][1]] = fares[i][2];
            dist[fares[i][1]][fares[i][0]] = fares[i][2];
        }

        //플로이드 알고리즘 이용
        findMinPath(n);

        //문제에서 요구하는 답 = min(d[s][k] + d[k][a] + d[k][b]) (단, k = 1 ~ n)
        int answer = Integer.MAX_VALUE;
        for (int k = 1; k <= n; k++) {
            if (dist[s][k] != INF && dist[k][a] != INF && dist[k][b] != INF) {
                answer = Math.min(answer, dist[s][k] + dist[k][a] + dist[k][b]);
            }
        }

        return answer;
    }

     private static void findMinPath(int n) {
        //dist[i][j] = i번 지점에서 j번 지점까지 갈 때의 최저 예상 택시요금
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

}