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

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

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를 출력하면 된다.

---

     한 정점에서 다른 정점까지의 최단거리를 구하는 문제로 다익스트라 알고리즘을 사용하면 된다. 주의할 점은 두 정점을 잇는 간선이 여러 개 있을 수 있다는 것과 단순 큐가 아닌 우선순위 큐를 활용하여 시간을 단축하지 않으면 시간 초과가 나게 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 987654321

using namespace std;
int v,e,k;
int dis[20001];
vector < pair<int,int> > adj[20001];

void solve(){
    dis[k] = 0;
    priority_queue < pair<int, int> > pq;
    pq.push(make_pair(0,k));
    while(!pq.empty()){
        int cur = pq.top().second;
        int curdis = -pq.top().first;
        pq.pop();
        if(curdis > dis[cur])
            continue;
        for(int i = 0; i < adj[cur].size(); i++){
            int next = adj[cur][i].second;
            int nextdis = curdis + adj[cur][i].first;
            if(dis[next] > nextdis){
                dis[next] = nextdis;
                pq.push(make_pair(-nextdis, next));
            }
        }
    }
}

int main (){
    int a, b, c;
    cin >> v >> e >> k;   
    for(int i = 1; i<= v; i++)
        dis[i] = INF;
    for(int i = 0 ; i < e ; i++){
        cin >> a >> b >> c;
        auto it = find_if(adj[a].begin(), adj[a].end(),
        [&b](const pair<int,int>& elem){return elem.second == b;});
        if(it == adj[a].end())
            adj[a].push_back(make_pair(c,b));
        else{
            if(it->first > c)
                it->first = c;
        }
    }
    solve();
    for(int i = 1; i <= v; i++){
        if(dis[i] != INF)
            cout << dis[i] << "\n";
        else
            cout << "INF\n";
    }
    
}

---

     처음에 자료구조를 인접행렬로 사용하여 메모리 초과가 났다. 배열을 선언할 때 싸한 느낌이 있었는데 무시하고 넘어갔더니 이런 사달이 나버렸다. 인접 리스트로 바꾸려던 중 생각을 해보니 한 정점에서 시작하는 것임에도 불구하고 플로이드 와샬 알고리즘을 활용하였던 것이었다. 그래서 다익스트라를 활용하면 되겠다고 생각을 한 순간 다익스트라 알고리즘이 떠오르지 않았다.. 분명 큐를 활용하여서 한 것 같은데  거기까지였다. 그래서 내가 쓴 이전 포스팅을 보면서 다익스트라를 다시 보았는데 그때도 문제 후기에 다익스트라가 생각나지 않았다고 적었던 것이다. 이 다익스트라는 두 번 쓰기는 쉬운데 한번 쓰기가 어려운 것 같다. 그렇게 다익스트라를 확신하며 제출을 하였는데 고려하지 못한 점이 있었다. 중복 검사를 하지 않았는데 생각해보니 find로 pair를 찾을 수가 없어 find_if를 활용하여 람다 함수를 이용하거나 별도의 함수를 작성하여 조건문을 사용해야 하였다. 이렇게 또다시 제출을 하였는데 또 틀리게 되었다! 알고 보니 -nextdis로 음수 값으로 절댓값이 작은 것의 우선순위를 높여 PQ를 이용하는 것 같아 보이지만 first가 정점 번호 여가 지고 우선순위가 거리로 잡히지 않았던 것이었다. first와 second를 바꾸어주니 정답을 받을 수 있었다. 이전에 푼 문제들에서는 똑같이 PQ를 설정하고 하였는데도 통과가 되어버린 것이 화근이었다. first를 정점 번호로 해주면 PQ 가 아닌 큐와 같아 그냥 BFS로 순회하는 것과 같은 시간이 소요된다고 한다! 돌다리도 두드려보고 건너야 한다는 것을 깨달은 문제였다..