백준 11779 최소비용 구하기 2 - C++, 다익스트라 경로추적

11779번: 최소비용 구하기 2

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

int n, m, start, finish;
int inputFrom, inputTo, inputCost;
vector<pair<int, int> > road[1001];
int city[1001];
int route[1001];
int main(){
    // 입력
    cin >> n >> m;
    for(int i = 1; i <= n; i++) city[i] = 999999999;
    while (m--){
        cin >> inputFrom >> inputTo >> inputCost;
        road[inputFrom].push_back(make_pair(inputTo, inputCost));
    }

    cin >> start >> finish;

    priority_queue<pair<int, int> > djikQ; // 비용, 지점 순
    djikQ.push(make_pair(0, start));
    city[start] = 0;

    while(!djikQ.empty()) {
        int cur = djikQ.top().second;
        int curCost = -djikQ.top().first;
        djikQ.pop();

        for(int i = 0; i < road[cur].size(); i++){
            int nextCur = road[cur][i].first;
            int nextCost = road[cur][i].second;

            if(city[nextCur] > curCost + nextCost){
                route[nextCur] = cur;
                city[nextCur] = curCost + nextCost;
                djikQ.push(make_pair(-city[nextCur], nextCur));
            }
        }
    }

    // 경로를 담을 벡터 선언
    vector<int> forPrint;
    int temp = finish;
    while(temp) {
        forPrint.push_back(temp);
        temp = route[temp];
    }
    int size = forPrint.size();
    // 출력 : 최소 비용, 경로에 있는 도시 수, 경로의 도시 순
    printf("%d\n", city[finish]);
    printf("%d\n", size);
    for(int i = size - 1; i >= 0; i--)
        printf("%d ", forPrint[i]);

}

---

시작과 도착 지점이 정해져 있는 것에서 다익스트라 알고리즘을 사용하면 되는 문제입니다. 대신 추가적으로 경로에 대한 정보가 필요해 route 배열을 하나 선언을 했으며 다익스트라 알고리즘을 하면서 다음 방문하는 곳을 인덱스로, 해당하는 값을 현재 지점으로 해서 이후 역추적이 가능하게 했습니다.

    while(temp) {
        forPrint.push_back(temp);
        temp = route[temp];
    }

이후 역추적에서 새로운 배열을 만들어 while 반복을 통해서 넣어주며 마지막 start에 도달하게 되면 그곳에는 값이 없어 루프를 나오게 됩니다. 이를 통해서 경로를 역추적할 수 있습니다.