합승 택시 요금

문제

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

---

문제 해결 아이디어

DP인데 '플로이드 워셜'이었던 것 점화식 구하는게 중요!

1. 그래프 구성
   • 주어진 fares 정보를 바탕으로 인접 행렬(dist 배열)을 생성
   • dist[i][j]는 i번 지점에서 j번 지점으로 이동하는 최소 요금을 저장
   • 직통 경로가 없으면 큰 값(주어진 조건을 만족하는 최대 거리)으로 초기화
   • 자기 자신으로의 이동 비용은 0으로 설정
2. Floyd-Warshall 알고리즘
   • 점화식: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]
   • 이 과정을 k=1..n, i=1..n, j=1..n에 대해 반복
3. 합승 지점 x 선택
   • 최종적으로 s(출발점)에서 x까지 함께 택시를 탄 뒤, x에서 A, B 각각의 집으로 따로 이동하는 경우를 고려
   • 즉, 모든 지점 x(1부터 n까지)를 순회하며, 비용 dist[s][x] + dist[x][a] + dist[x][b]의 최솟값

---

코드

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        // 1. dist 배열 초기화
        int[][] dist = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j) {
                    dist[i][j] = 20000000; // 최대 비용 (최대 요금 100,000 * 지점갯수 200 = 20,000,000)
                }
            }
        }

        // 2. 요금 정보 입력
        for (int[] fare : fares) {
            int c = fare[0];
            int d = fare[1];
            int f = fare[2];
            dist[c][d] = f;
            dist[d][c] = f;
        }

        // 3. Floyd-Warshall 알고리즘
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // 4. s→x 합승 후 x→a, x→b 각각 이동 비용의 최솟값 탐색
        int answer = dist[s][a] + dist[s][b]; // s→a + s→b 비용
        for (int x = 1; x <= n; x++) {
            int cost = dist[s][x] + dist[x][a] + dist[x][b];
            if (cost < answer) {
                answer = cost;
            }
        }

        return answer;
    }
}