[백준 1753] 최단경로(C++)

📕문제

방향 그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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를 출력하면 된다.

---

🔎문제해석

다익스트라 알고리즘을 이용해서 풀어야 하는 문제이다. 나는 인접 행렬 말고 인접 리스트를 사용해서 풀었다.

하지만 시간 초과... 완전 개박살 났다. 알고리즘 자체적으로는 문제가 없지만 C++ 언어 특성상 몇 개의 구문을 추가해주니 실행 속도가 월등히 빨라져서 풀 수 있었다. 만약 찾지 못했다면 정말 답이 없었을지도.. 밑에 구문이 내가 추가해준 구문이다.

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
out.tie(nullptr);

위의 구문에 대해서는 따로 글을 작성해서 자세히 알아볼 예정이다.

코드 자체는 완전 다익스트라 알고리즘이라 설명을 생략할 예정이다.

아마 정답률이 낮은 이유는 메모리 초과와 시간 초과 때문일 거라고 생각한다!!

 

📃코드

/*
백준 골드4 최단경로 
*/
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, s;
vector<int> d;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m >> s;
    vector<pair<int, int>> p[n + 1];
    d.resize(n + 1, INT_MAX);
    d[s] = 0;
    for (int i = 0; i < m; i++)
    {
        int start, finish, value;
        cin >> start >> finish >> value;
        p[start].push_back(make_pair(finish, value)); //이러면 같은 지역에 대한 다른 경로를 구분지어줘야함.
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> PQ;
    PQ.push(make_pair(0, s));
    while (0 != PQ.size())
    {
        auto now = PQ.top();
        PQ.pop();
        for (auto i : p[now.second])
        {
            if (i.second + now.first < d[i.first])
            {
                d[i.first] = i.second + now.first;
                PQ.push(make_pair(d[i.first], i.first));
            }
        }
    }
    for (int i = 1; i <= n; i++) //모든 거리 출력
    {
        if (d[i] == INT_MAX)
        {
            cout << "INF" << endl;
        }
        else
            cout << d[i] << endl;
    }
    return 0;
}

---

느낀점

• 메모리와 시간을 항상 염두에 두고 코드를 짜야하는데 그러지 못해서 시간이 많이 걸렸었다.
• 인접행렬과 인접리스트 둘 다 사용했지만 인접리스트가 더 코드를 짜기엔 어렵지만 효율성 측면에서 훨씬 유리해서 이제는 무조건 인접리스트로 짜야할듯?
• C++ 좀 별로야