[알고리즘 풀이 분석] BOJ 1753 최단경로

오늘 풀어본 문제는 BOJ 1753 최단경로 이다. 다익스트라를 연습하기 위해 풀어봤고 뜻밖의 메모리 초과를 만나 메모리 계산 연습이 더 필요한걸 느꼈다!

BOJ 1753 최단경로

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입출력

[입력]
첫째 줄에 정점의 개수 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를 출력하면 된다.

나의 풀이

매우 기본적인 다익스트라 사용 문제이다. 한 정점으로부터 다른 모든 정점까지의 최단 거리를 구하는 다익스트라 알고리즘 정의 그 자체이다.

주의할 점은 그래프 문제마다 보통 a->b 까지의 가중치가 b->a 가중치와 동일하게 처리되는 경우가 많았기 때문에 이 문제에서도 그렇게 착각했는데 아니었다! 역시,, 수백번 느끼는 조건 확인의 중요성,,

노드 수가 최대 20,000, 간선 수는 최대 300,000 개 였기 때문에 단순한 배열 탐색을 사용하면 안될 것이라 판단했고 priority_queue 를 사용해 minHeap 으로 활용하였다. priority_queue 는 기본적으로 maxHeap 으로 구현되어 있기 때문에 간선 값과 노드 번호를 쌍으로 묶어 오름차순으로 정렬하는 연산자를 구현해 minHeap으로 생성하였다.

이렇게 구현해서 제출했지만 메모리 초과가 떴다!

흠,, 시간 초과도 아니고 메모리 초과는 예상을 못했는데,,

질문 목록을 보니 나처럼 메모리 초과로 고생한 사람이 꽤 있는 것 같았다. 잘 모르겠지만 일단 뭐 가능한 모든 메모리를 줄여봤다.

애초에 그래프와 결과 배열은 입력되는 노드 수 V 만큼 동적 할당했기 때문에 문제가 없을 것 같았고 경로 값이 갱신되는 경우에만 minHeap 에 넣었기 때문에 이부분 역시 문제가 없을 것 같았다.

한가지 의심되는 부분은 V x V 개 만큼 할당한 그래프였는데,, 간선이 있던 없던 고정 크기의 2차원 배열이 사용되서 그러한가,, 싶었다.

그래서 2차원 배열을 버리고 vector<vector<pair<int,int>> edges 를 선언하였다. 입력되는 값이 5 1 1 과 같다면 edges[5].push_back(make_pair(1,1)) 과 같이 실행하여 존재하는 간선 값만 확인할 수 있도록 하였다.

거쳐가는 노드가 우선순위 큐의 꼭대기에서 꺼내지면 해당 노드가 간선을 가지고 있는 노드들에 대해서만 갱신을 시도했다.

이렇게 바꾸고 나니 통과 했고 올라와있는 질문들을 탐색하다가 간선값의 최대치를 INT_MAX 로 써주라고 하던데,, 문제 조건상에서 간선의 최대값이 10이기 때문에 11로 해주니 틀렸다고 나왔다! 결국 그냥 깔끔하게 INT_MAX 로 선언하여 통과하였다.

그냥 안전하게 최대값을 잡는게 역시 좋은듯,,

코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

vector<vector<pair<int, int>>> edges;

struct cmp {
    bool operator()(pair<int, int> & a, pair<int, int> & b){
        return a.first > b.first;
    }
};


void dijkstra(int V, int start){
    vector<int> path(V+1, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;  // 최소 힙 이용

    path[start] = 0;
    pq.push(make_pair(0, start));


    while (!pq.empty()){
        int cost = pq.top().first;  
        int node = pq.top().second;  // 거쳐갈 노드
        pq.pop();

        if (cost > path[node]) continue;  // // 거쳐갈 노드까지의 가중치가 현재 기준 최소값이 아니라면 pass 

        for (int i = 0; i < edges[node].size(); ++i) {  // 간선이 존재하는 노드들에 대해서만
            int dest = edges[node][i].first;
            int destCost = edges[node][i].second;

            if (path[dest] > cost + destCost){  // 갱신한다면 pq.push
                path[dest] = cost + destCost;
                pq.push(make_pair(path[dest], dest));
            }
        }
    }

    for (int i = 1; i <= V; ++i) {
        if (path[i] == INT_MAX) cout<<"INF";
        else cout<<path[i];
        cout<<"\n";
    }
}

int main() {

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

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

    edges.assign(V+1, vector<pair<int,int>>());

    for (int i = 0; i < E; ++i) {
        int from, to, weight;
        cin>>from>>to>>weight;

        edges[from].push_back(make_pair(to, weight));
    }

    dijkstra(V,K);

    return 0;
}