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

April 21, 2024

문제

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

설명

풀이

경우의 수는 다음과 같습니다.

s부터 동승해서 특정 노드로 가는 비용 + 해당 특정 노드에서 a로 가는 비용 + 해당 특정 노드에서 b로 가는 비용
동승하지 않아서, s부터 a로 가는 비용 + s부터 b로 가는 비용

모든 노드에서 모든 노드로 향햐는 최단 거리를 구할 수도 있습니다. (Floyd-Warshal)

그러나, 이 문제는 무방향 그래프이므로 한 노드에서 다른 노드로 가는 비용은 다른 노드에서 한 노드로 가는 비용과 동일합니다.

따라서 s, a, b 3개의 노드에서 모든 노드로 향하는 최단 거리만 구하면, 결과값을 찾을 수 있습니다. (Dijkstra 3번)

#include <bits/stdc++.h>

using namespace std;

int graph[202][202];

vector<int> dij(int n, int start) {
    vector<int> dist;
    dist.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        dist[i] = INT_MAX;
    
    dist[start] = 0; // 자신으로 가는 비용은 0
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.emplace(0, start); // 거리, 노드 번호
    
    while (!pq.empty()) {
        // 최소 비용으로 갈 수 있는 다음 노드
        int di = pq.top().first;
        int node = pq.top().second;
        pq.pop();
        for (int i = 1; i <= n; ++i) {
            if (graph[node][i] == INT_MAX) continue;
            if (dist[i] > di + graph[node][i]) {
                dist[i] = di + graph[node][i];
                pq.emplace(dist[i], i);
            }
        }
    }
    return dist;
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    for (const auto& fare : fares) {
        int c = fare[0], d = fare[1], f = fare[2];
        graph[c][d] = f;
        graph[d][c] = f;
    }
    for (int i = 1; i <= n; ++i) {
        for (int k = 1; k <= n; ++k) {
            if (graph[i][k] == 0)
                graph[i][k] = INT_MAX;
        }
        graph[i][i] = 0; // 자신으로 가는 비용은 0
    }
    auto sDist = dij(n, s);
    auto aDist = dij(n, a);
    auto bDist = dij(n, b);
    
    int result = INT_MAX;
    for (int i = 1; i <= n; ++i) {
        result = min(result, sDist[i] + aDist[i] + bDist[i]);
    }
    return result;
}