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

문제 설명

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

문제 풀이

• 플로이드 워셜 알고리즘을 이용하여 풀이하였다.
• 결과 도출을 위한 과정은 다음과 같다.

  • 플로이드 워셜 알고리즘을 이용해 모든 노드 사이의 최소 거리를 구한다.
  • 특정 K까지 합승한다는 가정하에 총 요금은 (S -> K) + (K -> A) + (K -> B)가 되므로 모든 K에 대해 반복하여 결과를 구한다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int INF = 987654321;
    public int[][] minDist;

    public int solution(int n, int s, int a, int b, int[][] fares) {
        //초기화
        minDist = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++)
            Arrays.fill(minDist[i], INF);
        for (int i = 0; i < fares.length; i++) {
            minDist[fares[i][0]][fares[i][1]] = fares[i][2];
            minDist[fares[i][1]][fares[i][0]] = fares[i][2];
        }

        //플로이드 워셜
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i == j) {
                        minDist[i][j] = 0;
                        continue;
                    }

                    if (i == k || j == k) continue;
                    minDist[i][j] = Math.min(minDist[i][j], minDist[i][k] + minDist[k][j]);
                }
            }
        }

        int res = INF;
        //결과 도출
        for (int i = 1; i <= n; i++) {
            if (minDist[s][i] == INF || minDist[i][a] == INF || minDist[i][b] == INF)
                continue;
            res = Math.min(res, minDist[s][i] + minDist[i][a] + minDist[i][b]);
        }
        return res;
    }
}