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

1. 문제

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

 

이 문제는 시작점 k부터 나머지 간선까지 최단 경로를 구하는 문제다. 정점과 간선의 개수는 1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000로 아주 큰 숫자다. 이를 주의해서 풀이해야 한다.

 

2. 문제 풀이

처음에는 다익스트라 알고리즘을 사용해서, 2차원 벡터 weight에 각각의 방향 그래프를 초기화하고, distance를 업데이트하는 방식을 사용했다. 이렇게 하니까 메모리 초과가 떴다. 그 이유는 위에선 언급한 것처럼, 정점과 간선의 개수가 너무 많은데, 불필요하게 weight를 (n+1) * (n+1) 크기를 갖도록 설정해 희소행렬이 되어버렸다. 

#include <iostream>
#include <vector>
#include <algorithm>

#define INF 9999

using namespace std;

int main() {
    int n, e, k; 
    cin >> n >> e >> k;

    
    vector<int> found(n+1, 0);
    vector<int> distance(n+1, INF);
    vector<vector<int> > weight(n+1, vector<int>(n+1, INF));

    for (int i = 1; i <= e; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        weight[u][v] = w;
    }

    distance[k] = 0;
        
    for (int i = 1; i <= n; i++) {
        int curr = -1, min_distance = INF; 
        for (int q = 1; q <= n; q++) {
            if (!found[q] && min_distance > distance[q] ) {
                min_distance = distance[q];
                curr = q;
            }
        }
        if (curr == -1) break;
        found[curr] = 1;

        for (int j = 1; j <= n; j++) {
            if (!found[j] && weight[curr][j] != INF) {
                distance[j] = min(distance[j], distance[curr] + weight[curr][j]);
            }
        }
    }

    // 0에서부터 i까지 최단 경로 출력
    for (int i = 1; i <= n; i++) {
        if (distance[i] == INF) {
            printf("INF\n");
        } else {
            printf("%d\n", distance[i]);
        }
    }
    return 0;
}

 

그래서 수정한 방법은, vector<vector<pair<int, int>>> weight(n+1)로 정의해서 인접리스트로 변경했다. 또, 간선을 모두 순회하는게 아니라 우선순위 큐를 사용해서 각각의 최단 경로를 계산했다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

#define INF 999999

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, e, k; 
    cin >> n >> e >> k;
    
    vector<int> distance(n+1, INF);
    vector<vector<pair<int, int> > > weight(n + 1);

    for (int i = 1; i <= e; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        weight[u].push_back({v, w});
    }

    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    pq.push({0, k}); 
    distance[k] = 0;

   while (!pq.empty()) {
        int dist = pq.top().first;
        int curr = pq.top().second;
        pq.pop();

        if (dist > distance[curr]) continue;

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

            if (distance[next] > distance[curr] + weight) {
                distance[next] = distance[curr] + weight;
                pq.push({distance[next], next});
            }
        }
    }


    // 0에서부터 i까지 최단 경로 출력
    for (int i = 1; i <= n; i++) {
        if (distance[i] == INF) {
            printf("INF\n");
        } else {
            printf("%d\n", distance[i]);
        }
    }
    return 0;
}