[Baekjoon] 1753번 최단경로.cpp

[백준] 1753번 최단경로 문제 링크

· 다익스트라 기본 개념

다익스트라 알고리즘의 기초가 되는 문제이다. 가중치가 있는 그래프에서 최단 경로를 찾는 해결법인 다익스트라는 아래와 같은 절차를 가진다.

1. 시작 노드와 연결된 노드와 연결된 다른 노드까지의 거리를 구한다.
2. 방문하지 않은 노드 중 시작 노드와 가장 가까운 거리에 있는 노드를 방문한다.
3. 해당 노드를 거쳐 더 짧은 거리로 이동할 수 있는 경로가 있다면 그 거리를 기록한다.

초기에 1번 과정을 한 번 거치고 모든 노드를 방문할 때까지 2, 3번 과정을 반복한다. 이때 단순하게 구현하면 그래프 연결 상태를 표현하기 위해 2차원 배열을 사용할 것이고, 가장 짧은 경로의 노드를 찾은 후 그 노드에 연결된 다른 노드들을 방문하여 최단 경로를 갱신해야 한다.

· 공간, 시간 복잡도

해당 문제에선 노드의 최대 갯수가 20,000개이다.

공간 복잡도 측면에선 단순 2차원 배열을 만들면 $20,000 * 20,000 = 400,000,000$개의 정수를 저장할 메모리가 필요하며, 각 1 bytes라 하여도 400 mb를 차지하게 되어 메모리 제한 256 mb를 초과한다.

시간 복잡도 측면에선 모든 노드를 방문하며 최단 경로를 갱신하기 때문에 기본적으로 $O(n)$의 시간이 걸리며, 방문할 노드를 찾기 위해 어떤 노드가 가장 짧은 거리를 갖는지 확인해야 하므로 $O(n)$의 연산을 매 노드를 방문할 때마다 처리해줘야 한다. 따라서 최대 $O(n^2)$의 시간 복잡도를 가져 4억 회의 연산이 필요하다고 할 수 있으므로 시간 제한 1초를 초과한다.

· 해결법

자료구조는 벡터 STL을 사용하여 각 노드에 연결된 간선의 갯수에 맞춰 공간을 할당해준다. 다만 가중치 정보가 존재하므로 { 가중치, 인접한 노드 } 정보를 pair 컨테이너에 저장하였다. 즉, 최대 간선 갯수인 600,000 개의 정수를 저장할 공간이면 충분하다.

알고리즘은 단순 탐색 대신 우선순위 큐를 이용하면 된다. <queue> 헤더의 priority_queue STL을 사용할 것이며, 우선순위 큐는 힙 자료구조를 이용하며 설정한 우선순위가 가장 높은 데이터가 컨테이너의 가장 앞에 위치하게 된다. 우리는 거리가 가장 짧은 것으로 우선순위를 설정할 것이지만, priority_queue STL은 큰 값을 최전방에 저장한다. 이러한 특징을 Max heap이라 한다. 이 특징을 이용하여 거리에 음수를 부여하여 큐에 삽입하면 부호가 없다고 생각했을 때 가장 작은 값이 최전방에 위치한다.

이후 큐에서 데이터를 하나씩 추출하며 해당 노드부터 인접한 노드를 찾아 추출한 데이터의 거리가 현재까지 갱신된 최소 거리보다 크지 않다면 인접한 노드 탐색을 시작한다.

이러한 방법을 사용하면 시작 노드의 인접 노드는 최대 $v$개이므로, 처음 우선순위 큐를 완성하는 시간 $O(v * logv)$에, 존재하는 모든 간선 정보를 큐에 삽입한다 해도 최대 $O(e * logn)$의 시간 복잡도를 가지므로 최악의 경우 $O((v + e) * log v)$의 시간 복잡도로 훨씬 적은 연산량을 가지게 된다.

위 말이 조금 어려울 수 있는데, 코드를 보면 이해가 쉽다. 아래는 벡터와 우선순위 큐를 이용한 최단경로 코드 전문이다.

#include <iostream>
#include <vector>
#include <queue>
#define MAX_SIZE 20001
#define INF 1000000000

std::vector<std::pair<int, int>> graph[MAX_SIZE];
int dist[MAX_SIZE];

std::priority_queue<std::pair<int, int>> pq;

int v, e;

void dijkstra(int startNode) {
	for (auto adj : graph[startNode]) {
		if (dist[adj.second] > adj.first) { // 문제에서 서로 다른 두 정점 사이에 여러 개의
			dist[adj.second] = adj.first;	// 간선이 존재할 수 있으므로 그 중 최소를 저장
		}
		pq.push({ -adj.first, adj.second });	// priority_queue STL은 max heap
	}

	dist[startNode] = 0;		// 시작 노드의 최소 거리는 0

	while (!pq.empty()) {		// 큐가 빌 때까지 반복
		int distance = -pq.top().first;	// 우선순위 큐에서 추출한 데이터의 음의 부호 제거
		int nodeNum = pq.top().second;
		pq.pop();

		if (distance > dist[nodeNum]) {	// 이미 방문한 노드이거나
			continue;							// 큐에 넣을 때보다 더 짧은 경로를 찾은 상태이면
		}										// 탐색하지 않고 다시 큐에서 데이터 추출

		for (auto adj : graph[nodeNum]) {
			if (dist[adj.second] > adj.first + distance) {
				dist[adj.second] = adj.first + distance;
				pq.push({ -dist[adj.second], adj.second });
			}
		}
	}
}

void init() {
	for (int count = 1; count <= v; count++) {
		dist[count] = INF;
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> v >> e;

	init();

	int startNode;
	int vert1, vert2, weight;

	std::cin >> startNode;
	
	for (int count = 0; count < e; count++) {
		std::cin >> vert1 >> vert2 >> weight;
		graph[vert1].push_back({ weight, vert2 });
	}

	dijkstra(startNode);

	for (int count = 1; count <= v; count++) {
		if (dist[count] == INF) {
			std::cout << "INF\n";
		}
		else {
			std::cout << dist[count] << "\n";
		}
	}
}