[C/C++] 백준 1753번(최단 경로) & 다익스트라 알고리즘

그래프 관련 문제는 DFS, BFS만 하다 오늘 새롭게 만나게 된 다익스트라 알고리즘을 이용해야 되는 문제를 풀게 되었고, 개념정리와 문제에 대한 풀이 이해를 위해 포스팅 해보았다.

문제

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

1753번: 최단경로

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제

풀이(코드)

#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <cctype>
#include <climits>

// Define
#define INF INT_MAX
#define MAX_IDX 20001

using namespace std;

// Global variable
int V, E, start;    // 정점 V, E, 시작노드 start
vector<pair<int, int>> g[MAX_IDX];  // 간선정보를 저장하는 g벡터
int dist[MAX_IDX];  // 시작점부터 index(= 정점 번호)까지 가는 거리에 대한 정보 저장

// Function
void init() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
void dijkstra() {
    // 코스트가 낮은 순으로 방문
    // 가중치, 시작 노드를 페어로 받음
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push({0, start});
    dist[start] = 0;    // 자기 자신으로 가는것이기에 0

    while (!pq.empty()) {
        int cost = pq.top().first;
        int curNode = pq.top().second;
        pq.pop();

        // 현재 노드와 연결된 노드들을 체크
        for(int i=0; i<g[curNode].size(); i++) {
            int nextNode = g[curNode][i].first;
            int nextCost = g[curNode][i].second;

            // 기존 값보다 경유하는것이 더 낮은 경우 업데이트
            if(dist[nextNode] > cost + nextCost) {
                dist[nextNode] = cost + nextCost;
                pq.push({dist[nextNode], nextNode});
            }
        }
    }
}

int main() {
    init();
    
    cin >> V >> E;
    cin >> start;

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

        // u 노드에서 v로 가는 가중치 w의 간선정보
        g[u].push_back({v, w}); 
    }

    // 거리를 담을 배열을 초기화
    // dist 배열은 start가 다른 idx까지 가는 최소비용을 저장
    for(int i=0; i<=V; i++) { dist[i] = INF; }

    dijkstra();

    // 출력
    for(int i=1; i<=V; i++) {
        if(dist[i] == INF) cout << "INF\n";
        else cout << dist[i] << "\n";
    }

    return 0;
}

 

다익스트라(Dijkstra)

 다익스트라는 DP 개념을 이용한 최단경로를 찾기 위해 사용되는 알고리즘이다. 다익스트라가 DP인 이유는 "특정 장소까지의 최단거리는 여러개의 최단거리들을 종합해서 얻는다", "최단거리는 이전까지 구했던 최단거리들을 기반으로 정한다" 같은 특징이 있기 때문이다. 특정한 정점에서 다른 정점까지 가는 최단 경로를 계산할 수 있기에 길찾기와 같은 서비스에서 사용될 수 있으며, 컴퓨터 네트워크에서 네트워크 라우팅, 컴퓨터 네트워크 프로토콜 등에서 사용될 수 있다.

동작 방식

1. 방문하지 않은 정점 중 가중치가 가장 적은 정점을 방문한다.
2. 만일 해당 정점을 방문해서 갈 수 있는 거리가 더 작다면 최소 거리를 업데이트 해준다.

e.g.
1~3까지 정점이 있고, (1 → 2) = 1, (1 → 3) = 4, (2 → 3) = 1
Start = 1
dist 배열을 이용. dist[2] = 1, dist[3] = 4, 나머지는 INF
    1. 거리가 가장 작은 2번 노드를 방문
    2. 2번 노드를 경유해서 가는 3번은 거리의 합이 2임이 확인
        2-1. dist[3] = 4 → dist[3] = 2 데이터 업데이트

주의점

다익스트라는 분명 주워진 경로들에 대한 데이터를 통해 최단경로를 구할 수 있지만 구현방식과 주워진 데이터에 따라 적합하지 않은 알고리즘이 될 수 있다. 

• 가중치가 음수일 경우 최적해가 나오지 않을 수 있다.
• 배열을 통해 구현할 경우 O(V^2)의 복잡도를 가진다.

 그렇기에 상황에 맞게 사용해야 된다.

 

 

p.s.
 요즘 동아리에서 "1일 1백준"이라는 꾸준히 백준 문제플기 스터디를 하고 있다. 사실 2년 전쯤 스터디 계획은 본인이 했었지만 당시 개발에 더 열중하고 싶어서 반년정도 운영하다가 후배친구에게 맡기고 본인은 나왔다 ㅋㅋㅋ. 그런데 한동안 안했더니 PS, 알고리즘 감을 잃어서 다시 같이 하고있다.