[프로그래머스] 합승 택시 요금 🚕 (Java)

🧩 문제 파악

• 택시 요금이 주어진 도시(그래프)에서 두 사람이 출발지 s에서 함께 택시를 타고 가다가 중간에 내려서 각자 a, b 목적지까지 가는 최소 비용을 구하는 문제이다!
• 두 사람은 언제든 분리되어 각자 목적지까지 갈 수 있고, 끝까지 같이 가도 된다.
• 택시 요금은 간선의 가중치로 주어지며, 양방향으로 이동 가능하다.

✅ 입력

• n : 지점(노드) 개수 (1 ≤ n ≤ 200)
• s : 출발 지점
• a : A의 도착 지점
• b : B의 도착 지점
• farces : 요금 정보 배열 [u, v, w] 형태 (w : u ↔ v 양방향 비용)

✅ 출력

• 두 사람이 탑승하다가 분리하여 목적지까지 가는 총 요금의 최소값

🎯 접근 방법

모든 지점(경유지 후보)을 순회하면서 해당 지점을 경유지로 선택했을 때 s → 경유지 + 경유지 → a + 경유지 → b 의 총 비용 중 최소값을 구한다.

그래프 표현 (인접 행렬)

• 크기가 작기 때문에 int[][] 인접 행렬로 그래프 표현
• costs[u][v] = w로 비용 저장 (양방향 처리)

  costs[fare[0]][fare[1]] = fare[2];
  costs[fare[1]][fare[0]] = fare[2];

다익스트라 3회 실행

• 합승 경유지를 i라고 한다면, 다음 3개의 비용의 합을 구해야 함.

  s → i (합승 비용)
  i → a (A 개인 비용)
  i → b (B 개인 비용)

• s, a, b각각을 시작점으로 다익스트라 실행 → 모든 노드까지 최소 비용 경로를 미리 구해둠.

• 다익스트라 흐름

  • 각 출발점 기준 dist[]배열을 INF로 초기화 후 dist[start] = 0
  • 우선순위 큐를 이용해 비용이 낮은 노드부터 탐색.
  • 현재 노드의 인접 노드들 중 dist[neighbor] > dist[current] + cost[current][neighbor]인 경우
    → 최소 비용 갱신 후 큐에 삽입.
  • 이 과정을 3회 반복하여 dist[0], dist[1], dist[2]에 각각 저장.

모든 경유지 후보에 대해 최소 비용

• 1부터 n까지 모든 노드를 경유지 후보에 두고,
  totalCost = dists[0][i] + dists[1][i] + dists[2][i]를 계산하여 최소값 갱신.

최소값 반환

• 모든 경유지 후보 중 최소 비용을 반환하여 두 사람의 합승 및 분리 이동 최소 비용을 구한다.

🌟 코드 구현

import java.util.*;

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        // 인접 비용 행렬 초기화 (0: 연결 X, 양수: 요금)
        int[][] costs = new int[n+1][n+1];
        for (int[] fare : fares) {
            costs[fare[0]][fare[1]] = fare[2];
            costs[fare[1]][fare[0]] = fare[2]; // 양방향
        }
        
        // dists[0] : s 기준 최소비용
        // dists[1] : a 기준 최소비용
        // dists[2] : b 기준 최소비용
        int[][] dists = new int[3][n+1];
        for (int[] dist : dists) {
            Arrays.fill(dist, Integer.MAX_VALUE); // INF로 초기화
        }
        
        final int[] start = {s, a, b}; // 출발점 3개
        
        // s, a, b 각각 다익스트라 수행하여 모든 노드까지 최소 비용 구하기
        for (int i = 0; i < 3; i++) {
            Queue<int[]> pq = new PriorityQueue<>((x, y) -> x[1] - y[1]); // 비용 오름차순
            int[] dist = dists[i]; // 현재 출발점 기준 최소 비용 배열
            pq.add(new int[]{start[i], 0}); // {현재 노드, 누적 비용}
            dist[start[i]] = 0; // 자기 자신까지 비용 0으로 설정

            // 다익스트라 실행
            while (!pq.isEmpty()) {
                int[] curr = pq.poll(); // 현재 {노드 번호, 누적 비용}

                for (int j = 1; j <= n; j++) {
                    if (costs[curr[0]][j] == 0) continue; // 연결 안된 경우 패스

                    int newDist = curr[1] + costs[curr[0]][j]; // 새로운 비용 계산
                    if (dist[j] > newDist) { // 더 적은 비용 발견 시 갱신
                        dist[j] = newDist;
                        pq.add(new int[]{j, newDist}); // 큐에 넣어 다음 탐색
                    }
                }
            }
        }
        
        // 합승 경유지 후보 i (1~n) 에 대해:
        // s -> i (합승) + i -> a + i -> b 최소 비용의 최소값 구하기
        int minCost = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            int sum = 0;
            for (int[] dist : dists) {
                sum += dist[i];
            }
            minCost = Math.min(minCost, sum);
        }

        // 최소 비용 반환
        return minCost;
    }
}