[백준][C++] 11779번: 최소비용 구하기2 <204>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

11779번: 최소비용 구하기 2

생각의 흐름

간단한 다익스트라 문제이다.

다만 역으로 추적하면서 지나온 경로를 기록하는 방식을 설명해볼까 한다.

 

이름이 road인 1차원 배열을 하나 만들었다.

road[now] = prev 의 의미는 "now번 정점에 최소 비용으로 도달하기 위해서는 prev정점으로 부터 왔습니다" 이다.

 

예를 들어보자. a 라는 시작점 에서 c 라는 도착지점 까지 최소비용으로 가야 하는데, 이 때 최소 비용의 경로가 a - b - c 라고 하자.

그렇게 되면, a에서 b를 선택하는 과정에서 road[b] = a, b에서 c를 선택하는 과정에서 road[c] = b 가 된다.

 

따라서 b까지 오는 최단 경로를 구한 시점에 b부터 역으로 road 배열을 추적해가면 된다.

c 를 오기 위해서 Route[c]를 확인하니 b가 존재

b 를 오기 위해서 Route[b]를 확인하니 a가 존재

a 를 오기 위해서 Route[a]를 확인하니 0이 존재.

0을 만났으니 종료!

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 1001
#define INF 987654321

int N, M;
int S, E;
vector<pair<int, int>> adj[MAX];
int dist[MAX];
int road[MAX];

void Dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    dist[start] = 0;

    while(!pq.empty()) {
        int nowCost = pq.top().first;
        int nowVertex = pq.top().second;
        pq.pop();

        if(nowCost > dist[nowVertex]) continue;
        
        for(auto e : adj[nowVertex]) {
            int nextCost = e.first;
            int nv = e.second;
            if(dist[nv] > nowCost + nextCost) {
                dist[nv] = nowCost + nextCost;
                road[nv] = nowVertex;
                pq.push({dist[nv], nv});
            }
        }
    }
}

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

    cin >> N >> M;
    int from, to, w;
    for(int i = 0; i < M; i++){
        cin >> from >> to >> w;
        adj[from].push_back({w, to}); // 일반 단방향 경로
    }
    cin >> S >> E;
    for (int i = 1; i <= N; i++) dist[i] = INF;
    Dijkstra(S);

    vector<int> roadVec;
    int num = E;
    while(num != 0) {
        roadVec.push_back(num);
        num = road[num];
    }

    cout << dist[E] << "\n";
    cout << roadVec.size() << "\n";
    for (int i = roadVec.size() - 1; i >= 0; i--) {
        cout << roadVec[i] << " ";
    }

    return 0;
}