[백준/BOJ] 1854번: K번재 최단경로 찾기( 다익스트라 알고리즘 ) - C++ 문제 풀이

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/1854

 

풀이

이 문제는 1번 도시에서 다른 도시까지 갈 수 있는 경로에 걸리는 시간 중에서 k번째 시간을 출력하는 문제입니다.

 

여기서는 한 도시에서 다른 도시까지 가는 데 걸리는 시간이 양수이므로, 다익스트라( Dijkstra ) 알고리즘을 사용합니다.

다익스트라 알고리즘에 관한 내용은 여기에서 볼 수 있습니다.

[C++] 최단 거리를 구하는 다익스트라( Dijkstra ) 알고리즘

 

그렇지만, 단순히 이동에 필요한 최단 시간을 구하는 것이 아니라, k번째 시간을 구해야 하므로, k개의 이동시간을 모아서, 그중 가장 큰 값을 구하면, 그 값이 k번째 시간이 될 것입니다.

만약, k번째의 이동시간이 없다면 -1을 출력합니다.

 

먼저, 주어진 입력 값으로부터 그래프를 구성합니다.

이때, 간선은 < 정점, 이동시간 > 쌍으로 나타낼 수 있습니다.

#define SIZE    1000
using Edge = pair<int, int>;    // < 정점, 거리 >

vector<Edge> graph[SIZE+1];

//----------------------------------------------------

int n, m, k;	// n: 정점 개수, m: 간선 개수, k: 원하는 이동거리의 순위
cin >> n >> m >> k;

int a, b, c;
for( int i = 0; i < m; i++){
    cin >> a >> b >> c;

    graph[a].emplace_back( b, c );	// 그래프 구성
}    

int start = 1;
dijkstra(start, k);	// 1번 도시부터 다른 도시까지의 이동거리 계산

 

다음은 다익스트라의 알고리즘을 약간 수정한 버전을 구현합니다.

// 정점에 도달하는 데 필요한 모든 시간 중, 최소의 시간부터 K번째까지만 기록
// 기록된 시간 중, 가장 오래 걸린 시간이 top에 위치
priority_queue< int > Dist[SIZE+1];   

struct myGreater{
    bool operator()( const Edge& a, const Edge& b){ // 내림차순
        return a.second > b.second;
    }
};


// K번째 걸리는 시간을 구하는 함수
void dijkstra(int start, int K){

    priority_queue< Edge, vector<Edge>, myGreater> q;  // 최소 힙

    Dist[start].push(0);
    q.emplace( start, 0);
    
    while(!q.empty()){

        const Edge& edge = q.top();
        
        int vert = edge.first;
        int dist = edge.second;

        q.pop();

        for( const auto& x : graph[vert]){
            
            int next = x.first;
            int nextDist = dist + x.second;

   	     // K개의 이동시간이 모이지 않으면, K개가 될 때까지 우선순위 큐에 저장
            if ( Dist[next].size() < K){
                Dist[next].push(nextDist);
                q.emplace(next, nextDist);
            }
   	     // K번째 이동시간보다 짧은 시간이 계산되면
  	     // K번째 이동시간 대신 짧은 시간을 우선순위 큐에 저장
            else if ( nextDist < Dist[next].top()){
                Dist[next].pop();
                Dist[next].push(nextDist);
                q.emplace(next, nextDist);
            }
        }  
    } 
}

Dist는 정점까지 도달하는 시간을 저장할 최대 힙( maximum heap ) 우선순위 큐입니다.

이 버퍼의 top에는 저장되어 있는 이동 시간 중, 최대 값이 위치합니다.

 

만약, K보다 적은 이동시간 횟수가 Dist에 입력되면, K번이 될 때까지 입력받습니다.

 

그러다 K 번째까지 시간이 다 찬 후에, 더 짧은 시간이 계산되면, 현재의 최대 값( top에 위치해 있음 )을 Dist에서 제거하고 새로운 시간을 대신 입력해 줍니다.

우선순위 큐는 입력과 동시에 자동으로 원소들을 정렬하기 때문에, 새로운 최대 값이 top에 위치합니다.

이 값이 K번째 이동 시간이 됩니다.

 

우선순위 큐( priority queue )에 관한 내용은 여기에서 볼 수 있습니다.

[C++] 우선 순위 큐 ( Priority Queue ) 사용법

 

마지막으로, dijkstra 함수가 종료되면, Dist의 top에 있는 값을 출력합니다.

이 값이 k번째 이동거립니다.

int start = 1;
dijkstra(start, k);	// 알고리즘 적용

for( int i = 1; i <= n; i++){
    
    if (Dist[i].size() < k)	// k번째 이동시간이 없으면 -1
        cout << -1 << endl;
    else{
        cout << Dist[i].top() << endl;	// k번째 이동시간 출력
    }
}

 

 

소스 코드

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

#define SIZE    1000
using Edge = pair<int, int>;    // < 정점, 거리 >

vector<Edge> graph[SIZE+1];

// 정점에 도달하는 모든 거리 중, 가장 작은 거리부터 K번째까지만 기록
// 기록된 거리 중,가장 먼 거리가 top에 위치
priority_queue< int > Dist[SIZE+1];   


struct myGreater{
    bool operator()( const Edge& a, const Edge& b){ // 내림차순
        return a.second > b.second;
    }
};


// K번째 먼 거리 구하는 함수
void dijkstra(int start, int K){

    priority_queue< Edge, vector<Edge>, myGreater> q;  // 최소 힙

    Dist[start].push(0);
    q.emplace( start, 0);
    
    while(!q.empty()){

        const Edge& edge = q.top();
        
        int vert = edge.first;
        int dist = edge.second;

        q.pop();

        for( const auto& x : graph[vert]){
            
            int next = x.first;
            int nextDist = dist + x.second;

            if ( Dist[next].size() < K){
                Dist[next].push(nextDist);
                q.emplace(next, nextDist);
            }
            else if ( nextDist < Dist[next].top()){
                Dist[next].pop();
                Dist[next].push(nextDist);
                q.emplace(next, nextDist);
            }
        }  
    } 
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m, k;
    cin >> n >> m >> k;

    int a, b, c;
    for( int i = 0; i < m; i++){
        cin >> a >> b >> c;

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

    int start = 1;
    dijkstra(start, k);

    for( int i = 1; i <= n; i++){
        
        if (Dist[i].size() < k)
            cout << -1 << endl;
        else{
            cout << Dist[i].top() << endl;
        }
    }

    return 0;
}