[C++] 백준 1753번: 최단경로

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

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

시작 정점에서 다른 모든 정점에 도달하는 최단거리를 구하여라.

---

시간복잡도 어림하기

 우선 문제에서 한 정점에서 출발하여 다른 모든 정점까지의 최단거리를 구하라고 했고, 가중치가 자연수 이므로 다익스트리 알고리즘을 사용하여 문제를 해결할 수 있습니다.

 

 다익스트라 알고리즘은 인접 행렬 또는 인접 리스트를 통해 구현할 수 있습니다. 만약, 인접 행렬로 구현한다면 20000 x 20000 = 4억 개의 공간이 필요합니다. 문제의 메모리 제한은 256MB이고 256MB = 2^8 x 2^20 B = 2^28B입니다. 배열에 int 값을 저장한다고 하면, 최대 2^28 / 4 = 2^26 = 약 6700만 개를 저장할 수 있습니다. 따라서 인접 리스트를 통해 그래프를 구현해야 합니다.

 

 또한, 다익스트라 알고리즘은 매 탐색마다 가장 가까운 정점을 찾아야 합니다. 이는 모든 정점을 탐색하는 알고리즘과 우선순위 큐를 사용하여 찾는 알고리즘을 통해 구현할 수 있습니다. 만약 모든 정점을 탐색한다면 시간 복잡도는 O(N) 이 될 것이고 우선순위 큐를 사용한다면 O(logN)의 시간복잡도를 가집니다. 매 시행마다 최대 20000번을 탐색한다면 시간 초과가 발생할 가능성이 높으니 우선순위 큐를 사용하여 구현해보겠습니다.

---

알고리즘 설계하기

 다익스트라 알고리즘은 다음과 같은 순서로 동작합니다.

1. 시작노드 방문 및 연결된 노드들에 대해 최단거리 갱신
2. 아직 방문하지 않은 노드 중 가장 가까운 노드 선택
3. 해당 노드 방문 및 연결된 노드들에 대해 최단거리 갱신
4. 2번으로 돌아가 반복

 

 가장 먼저 최단거리를 담을 배열인 dist 배열을 INF 값으로 초기화 합니다. INF는 임의의 아주 큰 수로 설정합니다. 이번 풀이에서는 1e9로 설정했습니다. 이후 시작 노드를 처리합니다. 시작 노드를 우선순위 큐에 {0, 시작 노드 번호}로 담습니다.

 

 우선순위 큐에 {거리, 노드 번호}로 담는 이유는 앞에 있는 값을 기준으로 먼저 정렬되기 때문입니다. 가장 가까운 노드를 찾기 위해서는 거리에 대해 먼저 정렬되어야 하므로 거리 값을 먼저 담아야 합니다.

 

 

 다음으로는 우선순위 큐가 빌때까지 다음 동작을 반복합니다.

 첫 동작은 우선순위 큐에 들어있는 노드 중 가장 가까운 노드를 찾는 것입니다. 우선순위 큐는 값을 push한 순간 곧바로 정렬되므로 우선순위 큐의 가장 위(top)에 있는 노드가 가장 가까운 노드가 됩니다.

 

 이때, 꺼낸 노드를 탐색할 필요가 없는지 확인하는 과정이 필요합니다. visited배열을 통해 각 노드를 방문처리 하여 구현할 수 있지만, 방문 상태를 담을 추가적인 공간이 필요하기 때문에 꺼낸 노드까지의 최단거리가 현재 갱신된 최단거리보다 크다면 무시하는 알고리즘을 사용할 것입니다.

 

 꺼낸 노드까지의 최단거리가 현재 갱신된 최단거리보다 크다는 말은 꺼낸 노드까지의 최단 경로가 발견되었다는 의미입니다. 따라서 최단거리가 아닌 경로에 대해 더 이상 탐색할 필요가 없습니다.

 

 

 마지막 동작은 꺼낸 노드와 연결된 노드들의 최단거리를 갱신하는 것입니다. 꺼낸 노드에 대해 인접 리스트를 탐색하면서 새로운 거리를 구해 기존 거리와 비교하는 방식으로 쉽게 구현할 수 있습니다.

 

 여기서 또 고민해야할 점은 노드와 노드 간의 가중치를 어떻게 찾을지 생각해봐야 합니다. 인접리스트를 통해 그래프를 구현하면 노드와 노드 간의 연결은 쉽게 찾을 수 있지만, 그 가중치는 바로 찾을 수 없습니다. 인접리스트를 통해 구현한 그래프에서 가중치를 찾기 위해서는 두 가지 방법을 사용할 수 있습니다.

 

 첫 번째 방법은 인접리스트를 <노드> : {노드, 노드, 노드}의 형태로 노드만 저장하는 것이 아닌 <노드> : {{노드, 가중치}, {노드, 가중치}, {노드, 가중치}} 와 같은 방식으로 노드와 가중치를 동시에 저장하는 방식을 사용할 수 있습니다.

 

 두 번째 방법은 map 자료구조를 사용하는 것입니다. map의 key로 {출발노드, 도착노드}로 설정하고 value를 가중치로 설정하여 구현할 수 있습니다. map을 사용하는 경우에는 같은 간선이 여러 개인 경우에는 가장 작은 값이 되도록 따로 처리가 필요합니다.

 

 이번 풀이에서는 map을 사용하여 구현해보겠습니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#include<queue>
#include<vector>
#include<map>
#define INF 1e9
using namespace std;

int v, e, dist[20004], st;
vector<int> adj[20004];
map<pair<int, int>, int> mp;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int main(){
    /*입출력 성능 향상*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> v >> e >> st;
    
    int from, to, weight;
    for(int i = 0; i < e; i++){
        cin >> from >> to >> weight;
        adj[from].push_back(to);
        if(mp[{from, to}] == 0 || mp[{from, to}] > weight) //중복된 간선인 경우 가중치가 작은 것으로 갱신
            mp[{from, to}] = weight; //map의 key가 pair인 경우 {값1, 값2}와 같은 방식으로 조회 가능
    }

    /*모든 최단거리 INF로 초기화*/
    fill(&dist[0], &dist[0] + 20004, INF);
    pq.push({0, st}); dist[st] = 0; //시작노드 처리
    
    while(!pq.empty()){
        int cur = pq.top().second; //가장 가까운 노드
        int d = pq.top().first; //가장 가까운 노드까지의 거리
        pq.pop();
        if(dist[cur] < d) continue; //현재 거리가 최단거리보다 큰 경우 -> 더이상 탐색할 필요 없음

        for(int next : adj[cur]){ //현재 노드와 연결된 노드들에 대해 최단거리 갱신
            int cost = dist[cur] + mp[{cur, next}]; //메모리 접근을 최소화하기 위해 미리 계산
            if(dist[next] > cost){
                dist[next] = cost;
                pq.push({cost, next}); //갱신한 거리를 다시 pq에 push
            }
        }
    }

    for(int i = 1; i <= v; i++){
        if(dist[i] == 1e9) cout << "INF" << '\n';
        else cout << dist[i] << '\n';
    }
    return 0;
}

 코드의 전체 흐름은 이전 단계에서 설명한 것과 동일합니다. 여기서 주의해야할 것은 pq에 {거리, 노드} 값을 push하는 위치입니다. pq에 값을 push할 때에는 최단거리 배열이 갱신이 된 경우일 때만 pq에 push해야 pq의 크기를 최소로 할 수 있습니다.

 또한, 꺼낸 노드에 대해 연결된 노드들의 최단거리를 갱신하는 for 루프에서 cost = dist[cur] + mp[{cur, next}]를 통해 미리 거리를 계산했는데, 이는 메모리 접근을 최소화 하기 위함입니다. 실제로 미리 계산하지 않고 cost 대신 dist[cur] + mp[{cur, next}]을 실행하면 시간초과가 발생합니다.

 항상 메모리 접근은 최소화할 수 있도록 하는 것이 예상치 못한 시간초과를 방지하는데 좋겠습니다.

---