백준 1753번 - 최단경로

백준 1753번 - 최단경로

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

1753번: 최단경로

최단경로 문제는 시간 복잡도가 1초이고 정점의 개수가 20000개, 간선의 개수가 300000개 이므로

단순한 그래프 문제 푸는 방식으로 풀게 되면 시간 초과가 나게 된다.

참고로 다익스트라 알고리즘의 시간 복잡도는 O((V+E)logV)이다.

 

다익스트라 알고리즘을 간단히 복습해 보자.

먼저 다익스트라 알고리즘의 특징은 간선의 가중치가 모두 양의 가중치여야 한다.

또한 한 정점에서 시작하여 모든 정점까지의 최단 거리를 구하는 알고리즘이다.

 

1. 각 정점과 그와 연결된 간선들의 정보를 저장

2. dist배열(거리)을 INF로 초기화(INF는 최댓값, 실무에서는 주로 배열의 원소 타입의 최댓값을 지정한다고 함)

3. 시작점의 dist를 0으로 초기화 후 우선순위 큐(priority queue)에 push 

4. 우선순위 큐의 top에 있는 정점을 방문한다. 이때 이미 방문한 정점인지를 확인한다.

   또 정점의 최단거리와 정점의 dist를 비교하여 가중치가 작거나 같을 때(다를 때!= 로 해도 된다고 합니다~)만 연산

   -> 이유를 잘 이해 못했었는데 쉽게 생각해 보면 가장 최단거리일 때만 계산하면 되기 때문이라고 이해했다.

5. 정점 방문 시 정점과 연결된 모든 정점들의 dist를 확인한다.

6. 만약 A->B 라 하면 dist [A] + Edge [A][B] < dist[B] 일 때만 dist[B] = dist[A] + Edge[A][B] 

7. 우선순위 큐에 대입

8. 4~7을 우선순위 큐가 빌 때까지 계속해서 반복

9. 도착 정점(최단거리를 구하고자 하는 정점)의 dist가 정답

 

 

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#pragma warning(disable:4996)
using namespace std;
 
bool check[20001];
vector<pair<int, int>>graph[20001];
 
int main() {
    int v, e, u, k, w;
    scanf("%d %d", &v, &e);
    scanf("%d", &k);
    int dis[20001];
    memset(dis, 127, sizeof(dis));
    int INF = dis[0];
    dis[k] = 0;
    int vertex;
    for (int i = 0; i < e; i++) {
        scanf("%d %d %d", &u, &vertex, &w);
        graph[u].push_back(make_pair(vertex, w));
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>> >pq;
    pq.push(make_pair(0, k));
    while (!pq.empty()) {
        int ver = pq.top().second;
        int wei = pq.top().first;
        pq.pop();
        if (check[ver] == true)continue;
        check[ver] = true;
        if (dis[ver] != wei)continue;
        for (int i = 0; i < graph[ver].size(); i++) {
            int a = graph[ver][i].second;
            int b = graph[ver][i].first;
            if (dis[ver] + a < dis[b]) {
                dis[b] = dis[ver] + a;
                pq.push(make_pair(dis[ver] + a, b));
            }
        }
    }
    for (int i = 1; i <= v; i++) {
        if (dis[i] == INF) printf("INF\n");
        else printf("%d\n", dis[i]);
    }
}

 

우선순위 큐에 pair <정점의 최단 거리, 정점>을 push 해야 되는데 반대로 해서 몇 번 틀렸었다..

또 dist [시작 정점] = 0인데 멍청하게도 시작 정점을 항상 1이라 생각하고 dist [1] = 0을 해서 틀렸었다

 

참고로 INF를 미리 저장해 놓는 게 꿀팁이라고 한다!!