[ 백준 11779 ] 최소비용 구하기2 (C++)

백준의 최소비용 구하기2(11779) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

양의 가중치만 존재하는 그래프에서 A도시에서 B도시 까지 가는데 걸리는 최소비용을 구해야 하는 문제이다.

동시에, 그 경로 또한 출력해야 하는 문제이다.

먼저, 최소비용을 구해야 하는 문제이고, 양의 가중치만 존재하는 문제이기 때문에 본인은 다익스트라 알고리즘으로

접근하였다. 아직 다익스트라 알고리즘에 대해서 잘 모른다면 아래의 글을 참고하도록 하자.

[ 다익스트라 알고리즘 알아보기 (Click) ]

다익스트라 알고리즘을 그대로 적용시키기만 하면 되는데, 그 경로 또한 출력해야 하기 때문에 본인은 경로를 저장할

int형 1차원 배열을 하나 선언해 주었다.

이 배열의 이름을' Route[]' 라고 가정해보자.

Route[a] = b 의 의미는 "a번 정점에 최소 비용으로 도달하기 위해서는 b정점에서 와야 합니다" 를 의미한다.

더욱 구체적으로 이야기를 해보자면, 'a'라는 정점에서 'c'라는 정점까지 최소비용으로 가야 하는데, 이 때 최소 비용이

드는 루트가 a - b - c 로 가는 루트라고 가정해보자.

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

최종적으로는, 이 Route배열을 다음과 같이 역추적을 해주면 된다.

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

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

'a'를 오기 위해서 Route[a]를 확인하니 '0'이 존재.(a가 시작점이였으므로 Route[a]의 값은 0이다)

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 1010
#define INF 987654321
using namespace std;
 
int N, M, Start, End;
int Dist[MAX];
int Route[MAX];
vector<pair<int, int>> V[MAX];
vector<int> Route_V;
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++) Dist[i] = INF;
    for (int i = 0; i < M; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        V[a].push_back(make_pair(b, c));
    }
    cin >> Start >> End;
}
 
void Solution()
{
    priority_queue<pair<int, int>> PQ;
    PQ.push(make_pair(0, Start));
    Dist[Start] = 0;
 
    while (PQ.empty() == 0)
    {
        int Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        for (int i = 0; i < V[Cur].size(); i++)
        {
            int Next = V[Cur][i].first;
            int nCost = V[Cur][i].second;
 
            if (Dist[Next] > Cost + nCost)
            {
                Route[Next] = Cur;
                Dist[Next] = Cost + nCost;
                PQ.push(make_pair(-Dist[Next], Next));
            }
        }
    }
 
    cout << Dist[End] << endl;
    int Temp = End;
    while (Temp)
    {
        Route_V.push_back(Temp);
        Temp = Route[Temp];
    }
    cout << Route_V.size() << endl;
    for (int i = Route_V.size() - 1; i >= 0; i--) cout << Route_V[i] << " ";
    cout << endl;
 
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}