[BOJ, C++]#1854_K번째 최단경로 찾기, 다익스트라, 길 찾기 알고리즘, 최단 경로 알고리즘, 단일-출발 최단 경로

#1. 문제

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

 

---

 

#2. 풀이

 

1. 다익스트라 알고리즘

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

다익스트라 알고리즘은 단일-출발 최단 경로를 찾기 위해 활용되며, 가중치 그래프에서 특정 정점을 시작으로 다른 모든 정점을 연결하는 경로 중 최소 가중치를 갖는 경로들을 찾는데 활용됩니다. 일반적으로, 다익스트라 알고리즘은 우선순위 큐와 최단 경로 목록을 활용합니다.

 

2. 풀이

1. 기존의 다익스트라 알고리즘과 달리 출발 정점으로부터 최단 경로를 저장하는 목록을 2차원으로 선언해 줍니다. 그리고 각 정점에 대하여 최단 경로 값을 K개만 기억하도록 크기를 설정해 줍니다.
2. 최단 경로 업데이트 시 K-1번째 최단 경로 값을 비교하고, 업데이트되었다면 sort 알고리즘 활용하여 K개의 최단 경로 값을 오름차순으로 정렬해 줍니다.
3. 마지막으로, K-1번째 최단 경로 값을 출력해 줍니다.

 

---

 

#3. 코드

@@ -0,0 +1,94 @@
/*
    @링크: https://www.acmicpc.net/problem/1854
*   @문제: K번째 최단경로 찾기
*   @설명
        1. 벨만-포드? 음수 가중치 없고, 딱히 순환 구조로 보이지도 않음
        2. 플로이드-워셜? 음수 가중치 없고, 입력 크기가 커보여서 좋지 않음
        3. 다익스트라: 단일-출발 최단 경로 알고리즘, 음의 가중치 없음, 무향/유향 둘다 활용 가능
        4. 최단 경로 값 목록 dist를 2차원 배열로 각 정점에 대하여 k개의 최단 경로 값을 갖도록 설정하고,
        k-1번째 최단 경로 값을 최신 값과 비교하여, 업데이트 여부 및 '정렬' 작업 수행.
*/

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

typedef pair<int,int> p;

int n, m, k;
vector<vector<p>> graph;

void dijkstra(int start)
{
    //@최단 경로
    vector<vector<int>> dist(n+1, vector<int>(k, INT_MAX));
    //@우선순위 큐
    priority_queue<p, vector<p>, greater<p>> pq;

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

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

        if(curDist > dist[cur][k-1]) continue;

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

            int newDist = curDist + weight;

            if(newDist < dist[next][k-1])
            {
                dist[next][k-1] = newDist;
                sort(begin(dist[next]), end(dist[next]));
                pq.push({newDist, next});
            }
        }
    }

    //@k번째 최단 경로 출력
    for(int i=1 ; i<=n; ++i)
    {
        if(dist[i][k-1] != INT_MAX)
        {
            cout << dist[i][k-1] << '\n';
        }
        else
        {
            cout << -1 << '\n';
        }
    }

}

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

    cin >> n >> m >> k;

    graph.resize(n+1);

    while(m--)
    {
        int a , b, c;
        cin >> a >> b >> c;

        graph[a].push_back({b,c});
    }

    dijkstra(1);

    return 0;
}

 

---