[2021 KAKAO BLIND RECRUITMENT]乗り合わせタクシー料金

2021 KAO BLIND RECRUITMENT合乗タクシー料金

を選択します。

グラフ

最短距離ナビゲーション(複数、flowersal)

問題を解く感覚をつかむために、まずココ公式問題解説を参考にしました.
問題を解く
この問題を解決するには、グラフィックの最短パスであるdijkstraアルゴリズムまたはFloyd-Warshalアルゴリズムを使用します.
2つのfloodアルゴリズムを使用して問題を解決したと仮定すると、すべての場所間のタクシー料金の最低推定値を次のように取得できます.
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]);
                }
            }
        }
    }

}