[BOJ알고리즘, C++]#11779_최소비용 구하기2, 최단 경로, 길 찾기, 다익스트라, BFS, 너비 우선 탐색

 

#1. 문제

https://www.acmicpc.net/problem/11779

 

---

 

#2. 풀이

 

1. 최단 경로 알고리즘

[알고리즘]#2_길 찾기 알고리즘

길 찾기 알고리즘은 가중치 그래프 내 출발점에서 도착점 사이의 경로 중 가중치의 합이 최소가 되는 경로를 찾는 아알고리즘입니다. 대표적인 최단 경로 알고리즘으로 다익스트라, 벨만-포드, 그리고 플로이드-워셜 알고리즘 등이 있습니다.

 

2. 다익스트라

[알고리즘]#2_길 찾기 알고리즘

다익스트라 알고리즘은 '단일-출발' 최단 경로를 찾는 알고리즘으로 간선의 방향성 유무에 따라서 상이하지만, 일반적으로 우선순위 큐와 BFS를 통해 구현합니다.

 

3. 다익스트라 과정에서 '부모 목록' 기억해 두자!

1. 먼저, '단일-쌍' 최단 경로를 구하기 위해 다익스트라를 구현합니다. 이때, 최단 경로 값 업데이트가 결정되면, 현재 노드를 인접 노드의 부모 노드로 기억해 둡니다.
2. 최소 비용을 구하고, 도착 노드를 시작으로 부모 노드를 타고 올라가며 방문 노드들을 '최소 비용'을 구성하는 도시들로 출력해 줍니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/11779
*   @문제: N개의 도시, M개의 도로, A -> B 경로의 최소 버스 비용.
*   @설명
        1. 최소 비용 : 다익스트라
        2. 최소 비용 경로의 도시 개수 : 부모 목록 추적, 도시 개수 출력
        3. 최소 비용 도시 순서대로 출력 : 부모 목록 추적, 역순으로 도시 출력
*/

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;

#define MAX 1001
typedef pair<int,int> p;

int N, M, start, dest, res;
vector<p> graph[MAX];
vector<int> dist(MAX, INT_MAX);
vector<int> parent(MAX, -1);

int dijkstra()
{
    priority_queue<p, vector<p>, greater<p>> pq;

    dist[start] = 0;
    pq.push({dist[start], start});

    while(!pq.empty())
    {
        int cur = pq.top().second;
        int weight = pq.top().first;
        pq.pop();

        if(weight > dist[cur]) continue;

        for(const auto& edge : graph[cur])
        {
            int neighbor = edge.first;
            int cost = edge.second;

            int newDist = weight + cost;
            if(newDist < dist[neighbor])
            {
                dist[neighbor] = newDist;
                parent[neighbor] = cur;
                pq.push({newDist, neighbor});
            }
        }
    }

    return dist[dest];
}

vector<int> getPath()
{
    vector<int> path;
    for(int at = dest; at != -1; at = parent[at])
    {
        path.push_back(at);
    }
    reverse(path.begin(), path.end());
    return path;
}

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

    cin >> N >> M;

    for(int i = 0; i < M; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }

    cin >> start >> dest;

    res = dijkstra();
    vector<int> path = getPath();

    cout << res << '\n';
    cout << path.size() << '\n';
    for(int city : path)
    {
        cout << city << ' ';
    }
    cout << '\n';

    return 0;
}

 

---