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

• 출처: 프로그래머스 72413
• 분류: 그래프 · Lv.3

문제

n개 지점, 출발지 s, A의 도착지 a, B의 도착지 b, 간선 요금 fares가 주어진다. s에서 출발해 A와 B가 각자 도착지까지 갈 때, 합승을 활용한 최저 택시요금을 반환한다. 합승하지 않는 것도 허용된다.

핵심

경유지 k까지 합승한 뒤 각자 이동한다고 하면, 비용은 dist_s[k] + dist_a[k] + dist_b[k]이다. s, a, b 각각에서 다익스트라를 돌려 모든 k에 대해 최솟값을 구한다.

풀이

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Node {
    int id, cost;
    bool operator>(const Node& o) const { return cost > o.cost; }
};

vector<int> dijkstra(int start, int n, vector<vector<pair<int,int>>>& adj) {
    vector<int> dist(n + 1, 1e9);
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    dist[start] = 0;
    pq.push({start, 0});

    while (!pq.empty()) {
        auto [u, d] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({v, dist[v]});
            }
        }
    }
    return dist;
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    vector<vector<pair<int,int>>> adj(n + 1);
    for (auto& f : fares) {
        adj[f[0]].push_back({f[1], f[2]});
        adj[f[1]].push_back({f[0], f[2]});
    }

    auto ds = dijkstra(s, n, adj);
    auto da = dijkstra(a, n, adj);
    auto db = dijkstra(b, n, adj);

    int answer = ds[a] + ds[b]; // 합승 안 하는 경우
    for (int k = 1; k <= n; k++) {
        answer = min(answer, ds[k] + da[k] + db[k]);
    }
    return answer;
}

메모

• 왜 다익스트라 3번인가
  • 합승 구간: s → k (비용 ds[k])
  • 개별 구간: k → a (비용 da[k]), k → b (비용 db[k])
  • 무방향 그래프이므로 a→k와 k→a의 비용이 같다. a에서 다익스트라를 돌리면 da[k] = a에서 k까지의 최단 거리 = k에서 a까지의 최단 거리
• 합승 안 하는 경우
  • k = s일 때 ds[s] + da[s] + db[s] = 0 + da[s] + db[s]로 자동 포함된다. 별도 처리 불필요
• Floyd-Warshall 대안
  • n ≤ 200이므로 Floyd-Warshall O(N³)로도 풀 수 있다. 200³ = 8,000,000
  • 다익스트라 3회는 O(3·(V+E) log V)로 더 빠르지만, 이 제약에서는 둘 다 통과한다
• 초기값 1e9
  • int에 1e9를 대입하면 1,000,000,000이다. 세 값을 더해도 3 × 10⁹으로 int 범위(~2.1 × 10⁹) 초과 가능성이 있다
  • 이 문제에서는 n ≤ 200, 요금 ≤ 100,000이므로 실제 최단 거리가 최대 ~20,000,000이라 오버플로우가 발생하지 않는다. 제약이 크면 long long을 쓴다

복잡도

풀이	시간	공간
Dijkstra × 3	O((V+E) log V)	O(V+E)
Floyd-Warshall	O(N³)	O(N²)