백준 g4 1753 최단경로 c++ (다익스트라)

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

1753번: 최단경로

 

다익스트라

매 단계마다 도달할 수 있는 정점 중에서, 시작점으로부터 거리가 가장 가까운 점을 구해서 그 거리를 확정 짓는 방법이다.

1. 노드 선택(시작점으로부터의 거리가 가장 가까운 노드)
2. 그 노드에서 뻗어나가는 간선들을 베이스로 인접한 노드들을 모두 업데이트
	원래 기록된 거리 vs. 1번에서 선택한 노드를 거쳤을 때의 거리 중 더 짧은 것으로 업데이트
		dist[인접한 노드] vs. dist[1번에서 선택한 노드] + adj[선택한 노드][인접한 노드]

1. 2. 번 과정을 더 이상 갈 수 있는 노드가 없을 때까지 반복하면 된다. 

예제를 가지고 그림으로 나타내면 다음과 같다.

 

밑에 있는 표는 시작점 ~ i번 노드까지의 거리를 나타낸 표이다.

0. 초기 상태

1에서 시작하므로 1의 dist는 0으로 둔다.

1. 1선택

dist 중 가장 작은 1을 선택한다. 1과 인접한 간선을 이용해 2와 3의 값을 업데이트 한다.

1은 확정되었고, 그 다음으로 작은 2를 선택해 확정한다.

2에서 뻗어나가는 간선을 가지고 인접한 노드를 업데이트 한다.

PQ로 시간 복잡도 줄이기

위에서 다익스트라를 소개한대로 구현하면 dist에서 가장 작은 노드를 선택할 때 O(V)만큼 탐색해야 하므로 전체 시간 복잡도는 O(V*V+E)가 된다. (가장 작은 노드 탐색 V*이를 노드 개수 V만큼 반복 + 총 E개의 간선으로 업데이트)

그렇지만 가장 작은 노드를 탐색하는 과정을 PQ에 넣어서 관리하면 O(ElogE)로 풀 수 있다. (PQ에 E개의 간선이 들어감)

 

1번에서 갈 수 있는 dist 중 가장 작은 노드를 선택하는 것이 아니라, 인접해서 업데이트된 노드들의 값을 PQ에 넣는다. 

 

다익스트라 알고리즘이 항상 최단 거리인 이유 + 음수인 간선이 있으면 쓸 수 없는 이유

예를 들어 dist배열에서 가장 짧은 3번 노드를 골랐다고 해보자. 이때 우리는 1번 -> 3번 노드의 거리를 확정한다.

만약 이때 확정한 3번 노드의 거리가 최단 거리가 아니려면, 예를 들어 2번 노드를 거쳐야 3번노드가 최소 거리가 된다고 가정해보자.

그러나 1번 노드 -> 2번 노드 -> 3번 노드로 거쳐 가는 것이 3번 노드의 최단 거리라면, 3번 노드가 선택되기 전에 2번 노드가 먼저 선택되었어야 했다. (1 -> 3보다 1 -> 2 -> 3이 더 짧으므로) 그러므로 모순

 

그래서 음수 간선이 있으면 다익스트라 알고리즘을 쓸 수 없다.

 

풀이(구현)

vector<pair<int, int>> adj[MAXN]; // 비용, 노드 번호
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> PQ;
int dist[MAXN];

비용 + 인접 리스트를 담을 adj 배열, 가장 작은 간선을 알려줄 PQ 배열, dist를 담을 배열이 필요하다.

// 1. 시작점 넣기
dist[start] = 0;
PQ.push({0, start});

// 2. 다익스트라 진행
int cost, num;
while (!PQ.empty()) {
    tie(cost, num) = PQ.top();
    PQ.pop();

    if (dist[num] != cost) continue;

    for (pair<int, int> a : adj[num]) {
        if (dist[a.second] > dist[num] + a.first) {
            dist[a.second] = dist[num] + a.first;
            PQ.push({dist[a.second], a.second});
        }
    }
}

 

만약 dist값과 PQ에서 꺼낸 cost값이 같지 않으면 continue 한다. (이게 vis와 같은 역할을 하는데, 만약 dist값이 작아져서 바뀌었다면 굳이 이전의 큰 dist값으로 처리를 해줄 필요가 없기 때문이다. 문제에서 서로 다른 두 정점 사이에 간선이 여러 개 있을 수 있다고 했는데, 여기서 걸러진다)

 

나머지는 위에서 말한 1. 노드를 선택한다 (PQ) 2. 노드와 인접한 노드들의 값을 업데이트하고 PQ에 넣는다. 이대로 구현하면 된다.

 

전체 코드

/*boj g4 1753 최단경로(다익스트라)*/
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
#define MAXN 20005
#define INF 1e9 + 10
using namespace std;

int V, E;
int start;
vector<pair<int, int>> adj[MAXN]; // 비용, 노드 번호
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> PQ;
int dist[MAXN];

void input() {
    cin >> V >> E;
    cin >> start;

    for (int i = 0; i < E; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        adj[u].push_back({w, v});
    }
}

void initialize() {
    for (int i = 0; i <= V; i++) {
        dist[i] = INF;
    }
}
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    initialize();

    // 1. 시작점 넣기
    dist[start] = 0;
    PQ.push({0, start});

    // 2. 다익스트라 진행
    int cost, num;
    while (!PQ.empty()) {
        tie(cost, num) = PQ.top();
        PQ.pop();

        if (dist[num] != cost) continue;

        for (pair<int, int> a : adj[num]) {
            if (dist[a.second] > dist[num] + a.first) {
                dist[a.second] = dist[num] + a.first;
                PQ.push({dist[a.second], a.second});
            }
        }
    }

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