[BOJ 11779 // C++] 최소비용 구하기 2

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 11779번 문제인 최소비용 구하기 2이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

이 문제에서는 다익스트라(dijkstra) 알고리즘을 이용해 최단경로를 찾으면서, 그 최단경로에서 지나온 노드를 하나하나 출력해줘야 한다.

 

다익스트라 알고리즘을 실행하면 출발점에서 각 노드까지의 최단 거리를 얻을 수 있는데, 그 경로를 이으면 출발점을 root로 갖는 트리구조를 얻을 수 있다.

 

여기서, 도착지점 노드에서 조상(parent) 노드를 출발점 노드인 root 노드까지 하나씩 거슬러 올라가면서 만나는 노드들이 바로 출발지점 노드에서 도착지점 노드까지 가는 최단경로에 있는 노드들이 된다.

 

따라서, dijkstra를 하면서 priority queue에 다음 방문우선순위를 집어넣을 때, 그 노드의 parent node를 갱신하는 방식으로 알고리즘을 만들면 이 문제는 해결 가능하다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using std::cin;
using std::cout;
using std::priority_queue;
using std::vector;
using std::pair;

vector<pair<int, int>> G[1001];
priority_queue<pair<int, int>> pq;
int dist[1001];
int parent[1001];
bool done[1001];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;
    for (int i = 0;i < M;i++) {
        int s, e, w; cin >> s >> e >> w;
        G[s].push_back({ e,w });
    }
    int S, E;
    cin >> S >> E;
    for (int i = 1;i <= N;i++) {
        dist[i] = 1000000000;
    }
    dist[S] = 0;
    parent[S] = S;
    pq.push({ 0,S });
    while (!pq.empty()) { // dijkstra
        int current = pq.top().second; pq.pop();
        if (done[current]) continue;
        else if (current == E) break;
        done[current] = true;
        for (auto following : G[current]) {
            int fnode = following.first;
            int fweight = following.second;
            if (dist[fnode] > dist[current] + fweight) {
                dist[fnode] = dist[current] + fweight;
                pq.push({ -dist[fnode],fnode });
                parent[fnode] = current; // parent 정보 갱신
            }
        }
    }
    cout << dist[E] << "\n";
    vector<int> stk; // 역순 출력을 위해 stack에 담기
    while (E != parent[E]) { // parent[S]=S, 나머지 점에서는 각 노드의 조상
        stk.push_back(E);
        E = parent[E];
    }
    stk.push_back(E); // root 노드를 넣어준다
    cout << stk.size() << "\n";
    while (!stk.empty()) {
        cout << stk.back() << ' ';
        stk.pop_back();
    }
}