[백준 11779] 최소비용 구하기 2

🔗 알고리즘 문제

기본적인 다익스트라 문제이지만 경로를 역추적하는 아이디어를 깔끔하게 생각해내기가 쉽지 않아 다소 어려웠던 문제이다.

문제 분석

이 문제는 그래프의 정보와 시작점, 끝점이 순차적으로 주어질 때 시작점에서 끝점까지 이동하는 최소비용과 그 때에 이동 횟수와 이동 경로를 출력하는 문제이다.

다음과 같은 그래프에서 시작점을 1 끝점을 5로 둔다고 한다면

최단 거리 : 4

이동 횟수 : 3
이동 경로 : 1->3->5  \  1->4->5

이런식의 결과가 나오게 된다.

발상 & 알고리즘 설계

최단 거리는 단순 다익스트라로 구할 수 있지만, 이동 경로를 구해내는 것이 좀처럼 아이디어가 떠오르지 않았다.

끝점에 도달했을 때 다시 반대로 역추적하는 방법도 생각해보았지만, 이 방법은 비효율적이라고 느껴졌다. 고민 끝에 각 노드마다 자신의 이동 경로를 가지고 있도록 하는 방법을 생각해내었다.

class Val{
	int dis; // 해당 노드까지의 비용
    int idx; // 해당 노드의 번호
    vector<int> vt; // 해당 노드까지의 경로
}

비용과 번호 그리고 해당 노드까지의 경로를 담고 있는 클래스를 만들어 끝점에 도달했을 때 끝점이 가지고 있는 vt속 경로를 출력해주었다.

코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<climits>

using namespace std;

class val{
public:
    val(int dis, int idx, vector<int> vt){
        this->dis = dis;
        this->idx = idx;
        this->vt = vector<int>();
        for(int i = 0; i < vt.size(); i++){
            this->vt.push_back(vt[i]);
        }
    }

public:
    int dis;
    int idx;
    vector<int> vt;
};

struct comp{
    bool operator()(val& a, val& b){
        return a.dis > b.dis;
    }
};

int main(){
    vector<pair<int, int>> v[1001] = {};
    int check[1001] = {};

    int n;
    int m;

    cin >> n >> m;

    for(int i = 0; i < m; i++){
        int from;
        int to;
        int cost;

        cin >> from >> to >> cost;

        v[from].emplace_back(to, cost);
    }

    int sv;
    int ev;

    cin >> sv >> ev;

    priority_queue<val, vector<val>, comp> pq;
    val start(0, sv, vector<int>());
    pq.push(start);
    check[sv] = 0;

    fill(check, check + 1001, INT_MAX);

    while(!pq.empty()){
        val node = pq.top();
        pq.pop();

        if(node.idx == ev){
            cout << node.dis << "\n";
            cout << node.vt.size() + 1 << "\n";
            for(int i = 0; i < node.vt.size(); i++){
                cout << node.vt[i] << " ";
            }
            cout << ev;
            break;
        }

        for(int i = 0; i < v[node.idx].size(); i++){
            val next(v[node.idx][i].second + node.dis, v[node.idx][i].first, node.vt);

            if(next.dis < check[next.idx]){
                check[next.idx] = next.dis;
                next.vt.push_back(node.idx);
                pq.emplace(next);
            }
        }
    }
}