[BOJ] 11779번 | 최소비용 구하기 2 (C++)

🔗문제 보러가기

11779번: 최소비용 구하기 2

 

🧑‍💻풀이 과정

 

기본적인 틀은 다익스트라 알고리즘인데, 최단 경로에 해당하는 각 도시들 번호를 어떻게 저장할 지가 문제였습니다. 분기가 이루어지는 각 경로마다 자기가 거쳐 온 도시 정보를 가지고 있을까 생각했다가, 메모리가 너무 많이 들 것은 물론 복사 비용이 만만치 않을 것 같아 포기했습니다.

 

그래서 결국 다른 분의 풀이를 참고했는데, 배열을 통해 이전 노드로 가는 길을 추적하는 참신한 방법을 사용하여 푸셔서 놀랐습니다. 예를 들어, arr[a] = b 라는 것은 a 도시로 오기 위한 이전 도시는 b 도시라는 것을 의미하죠.

 

최단 경로에 해당하는 최소 비용을 갱신할 때, 해당 도시에 대해 거치는 이전 도시 정보만 갱신해주면 되었습니다.

목적지 도시에서 출발 도시로 거꾸로 추적해 들어가는 것이기 때문에, 스택(Stack)에 담아 출력하였구요.

 

참고하면 좋을 점

 

예제의 1번 도시 👉🏻 5번 도시로 가는 최단 경로는 1 👉🏻 3 👉🏻 5 라고 되어 있는데, 1 👉🏻 4 👉🏻 5 도 정답인 경로입니다. 저 같은 경우에는 1 👉🏻 4 👉🏻 5 가 출력이 되었는데 정답 처리를 해주는 걸 보니, 여러 최단 경로 중 하나만 출력하면 되는 듯해 보입니다. 

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;
using uint32 = unsigned int;
using Info = pair<uint32, uint32>;    // <비용, 목적지>

#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
#define MAX 3000000000

vector<uint32> Costs;

stack<int> Dijkstra(const vector<vector<Info>>& routes, const uint32 N, uint32 startCity, uint32 destinationCity) {
    vector<uint32> traces(N + 1);
    priority_queue<Info, vector<Info>, greater<Info>> pq;

    Costs[startCity] = 0;
    pq.emplace(0, startCity);

    while (!pq.empty()) {
        uint32 cost = pq.top().first;
        uint32 city = pq.top().second;
        pq.pop();

        if (Costs[city] < cost)
            continue;
        
        for (const auto& adjacentCity : routes[city]) {
            uint32 nextCost = cost + adjacentCity.first;
            uint32 nextCity = adjacentCity.second;

            if (nextCost < Costs[nextCity]) {
                Costs[nextCity] = nextCost;
                traces[nextCity] = city;
                pq.emplace(nextCost, nextCity);
            }
        }
    }

    stack<int> answers;
    uint32 city = destinationCity;
    answers.push(city);

    while (traces[city] != 0) {
        answers.push(traces[city]);
        city = traces[city];
    }

    return answers;
}

int main() {
    FAST_IO
    uint32 n, m, from, to, cost;
    cin >> n >> m;

    vector<vector<Info>> busRoutes(n + 1, vector<Info>());
    Costs.resize(n + 1, MAX);

    for (int i = 0; i < m; i++) {
        cin >> from >> to >> cost;
        busRoutes[from].emplace_back(cost, to);
    }

    uint32 startCity, destinationCity;
    cin >> startCity >> destinationCity;

    stack<int> routes = Dijkstra(busRoutes, n, startCity, destinationCity);
    
    cout << Costs[destinationCity] << "\n";
    cout << routes.size() << "\n";

    while (!routes.empty()) {
        cout << routes.top() << " ";
        routes.pop();
    }

    return 0;
}