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

문제 설명

 

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

 

풀이

이 문제는 출발 노드로부터 도달이 가능한 모든 노드들까지의 최단 거리를 구하는 문제입니다.

 

이 문제를 해결할 수 있는 알고리즘으로 다익스트라( Dijkstra )와 벨만-포드( Bellman-Ford) 알고리즘이 있습니다.

그런데, 간선의 가중치가 양수인 경우, 다익스트라 알고리즘이 좀 더 빠릅니다.

 

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

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

 

이 알고리즘을 사용하기 위해서 먼저 그래프를 구성합니다.

#define SIZE    20000
using Edge = pair<int, int>;	// 별명 사용

vector<Edge> graph[SIZE+1];
int minDist[SIZE+1];	// 노드까지의 최단 거리 저장
bool visited[SIZE+1];

int main(){

    int V, E;
    cin >> V >> E;

    int start;
    cin >> start;	// 출발 노드

    int a, b, w;
    for( int i = 0; i < E; i++){	// 그래프 구성
        cin >> a >> b >> w;

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

    dijkstra(start, V);	// 알고리즘 실행

    for( int i = 1; i <= V; i++){	// 각 노드까지의 최단 거리 출력
        if (!visited[i])
            cout << "INF" << endl;
        else
            cout << minDist[i] << endl;
    }

    return 0;
}

각 간선은 노드와, 그 노드까지의 거리( 가중치 )를 쌍으로 하는 pair 구조체로 이루어져 있습니다.

 

또, 간선을 그래프 vector에 저장할 때, pair 객체의 복사를 막기 위해 empace_back 함수를 사용하였습니다.

emplace 함수의 사용법은 여기에서 볼 수 있습니다.

[C++] STL emplace 함수 설명 및 사용법

 

다익스트라( Dijkstra ) 알고리즘을 코드로 작성한 것은 다음과 같습니다.

struct myComp{	// 사용자 함수 객체

    bool operator()( const Edge& a, const Edge& b){
        return a.second > b.second;
    }
};

void dijkstra(int start, int vect_cnt){

    priority_queue< Edge, vector<Edge>, myComp> q;  // 내림차순

    for( int i = 1; i <= vect_cnt; i++){
        minDist[i] = INT_MAX;  // 초기화
    }

    minDist[start] = 0;	// 시작 정점의 최단 거리는 0
    q.emplace( start, 0);
    
    while(!q.empty()){

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

        q.pop();

        if ( visited[vert])	// 방문한 정점을 재방문할 필요가 없음
            continue;

        visited[vert] = true;

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

    	    // 이전의 최단거리와 새로운 최단 거리를 비교
            if ( nextDist < minDist[next]){
                minDist[next] = nextDist;
                q.emplace( next, minDist[next]);
            }
        }  
    } 
}

우선순위 큐로 "거리 기준" 최소 힙( minimum heap )을 구성했습니다.

최소 힙은 가장 작은 값을 가진 원소가 top에 위치하는 자료 구조입니다.

 

이 우선순위 큐에 간선을 저장하면, 자동으로 가장 작은 최단 거리를 가진 원소가 top에 위치합니다.

따로 정렬할 필요가 없으므로 편리합니다.

 

그런데, 최소 힙을 구성하려면, 내림차순으로 원소들을 정렬해야 합니다.

C++에서 제공하는 greater 함수 객체를 사용하면 pair의 first의 값을 기준으로 정렬합니다.

하지만, < 노드, 가중치 > 순으로 사용하는 것이 받아들이기에 익숙하므로, 사용자 함수 객체를 사용하여 pair의 second 값을 기준으로 정렬했습니다.

 

우선순위 큐 사용법에 대한 자세한 내용은 여기서 볼 수 있습니다.

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

 

이 함수가 종료되면, minDist 배열에 출발 노드로부터 다른 노드까지의 최단 거리가 저장됩니다.

 

소스 코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h> // for INT_MAX
using namespace std;

#define SIZE    20000
using Edge = pair<int, int>;

vector<Edge> graph[SIZE+1];
int minDist[SIZE+1];
bool visited[SIZE+1];

struct myComp{

    bool operator()( const Edge& a, const Edge& b){
        return a.second > b.second;
    }
};

void dijkstra(int start, int vect_cnt){

    priority_queue< Edge, vector<Edge>, myComp> q;  // 내림차순

    for( int i = 1; i <= vect_cnt; i++){
        minDist[i] = INT_MAX;  // 초기화
    }

    minDist[start] = 0;
    q.emplace( start, 0);
    
    while(!q.empty()){

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

        q.pop();

        if ( visited[vert])
            continue;

        visited[vert] = true;

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

            if ( nextDist < minDist[next]){
                minDist[next] = nextDist;
                q.emplace( next, minDist[next]);
            }
        }  
    } 
}

int main(){

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

    int V, E;
    cin >> V >> E;

    int start;
    cin >> start;

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

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

    dijkstra(start, V);

    for( int i = 1; i <= V; i++){
        if (!visited[i])
            cout << "INF" << endl;
        else
            cout << minDist[i] << endl;
    }

    return 0;
}