BOJ 백준 1753 최단경로

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

<최단 경로>

 이 문제의 입력은 총 정점의 수와 간선의 수, 시작할 정점과 각 간선들에 대한 정보가 주어진다.

간선의 방향이 존재하며, 시작 정점으로부터 다른 모든 정점들에 대해 최단 경로를 출력해주어야 한다.

다익스트라 문제는 종종 풀었으나, 우선순위 큐를 이용하여 푼 적은 거의 없었다.

이 문제도 보자마자 다익스트라를 사용했고, 결과는 시간 초과였다.

메모리 제한 : 256MB

시간 제한 : 1초

우선 정점의 수가 최대 20000개이므로 일반 배열, 즉 20000 * 20000의 int형 배열로는 메모리 초과가 난다.

그래서 vector을 이용하여, 간선의 정보가 주어지면 push해주는 방법을 이용했다.

난 단순히 메모리초과만 생각하고 벡터로 한 뒤 코딩을 했는데, 내가 기존 우선순위 큐를 이용하지 않고 푸는

알고리즘의 시간 복잡도는 O(V^2) 이다.

모든 정점에 대해 가중치가 저장되어 있는 dist 배열에서 가장 적은 가중치를 찾고, 이를 모든 정점에 대해 시행하므로 V^2이다.

위의 문제는 정점의 개수가 매우 많으므로, 내가 본래 풀던 방식의 시간 복잡도인 V^2로는 시간 초과가 난다.

따라서, 우선순위 큐를 이용한 풀이가 필요하다.

우선순위 큐를 이용한 다익스트라 알고리즘의 시간복잡도는 중복 간선이 없다면 O(ElogV), 있다면 O(ElogE)로 보는 것 같다.

중복간선이 없는 경우 보통 E < V^2 이므로, logE = logV^2,   2logV는 O(logV)로 되기 때문이다.

(위의 시간복잡도를 이해하기 위한 추가 공부 필요)

우선순위 큐는 < 가중치, 정점 > 로 이루어져 있는데, 푸쉬할 때 가중치에 대해 -를 붙여 푸쉬한다. 이 이유는 우선순위 큐가 

큰 숫자부터 정렬해나가기 때문에, -를 붙여 가장 작은 가중치가 먼저 처리되도록 하기 위함이다.

pq.push({ -cost, vtx } ); 로 푸쉬하고, top()으로 받아올 때 다시 -를 붙여 +로 바꾸어 준다.

이런 식이 아닌, 우선순위 큐를 선언할 때 priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > pq;

로 선언해주어 오름차순으로 정렬되도록 해도 된다.

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

#define SIZE 20001
#define INF 1000000000

using namespace std;

vector< pair<int, int> > vtx[SIZE];
int vtx_num, edge_num, start_node;
int dist[SIZE];

void dijkstra()
{
	for (int i = 1; i <= vtx_num; ++i)
	{
		dist[i] = INF;
	}
	dist[start_node] = 0;

	
	priority_queue< pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>> > pq;
	
	pq.push({ 0, start_node });

	while (!pq.empty())
	{
		int		iCost = pq.top().first;
		int		iCur_node = pq.top().second;
		pq.pop();

		if (dist[iCur_node] < iCost) continue;
		
		for (int i = 0; i < vtx[iCur_node].size(); ++i)
		{
			int next_node = vtx[iCur_node][i].first;
			int next_cost = iCost + vtx[iCur_node][i].second;

			if (dist[next_node] > next_cost)
			{
				dist[next_node] = next_cost;
				pq.push({next_cost, next_node});
			}
		}
	}

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> vtx_num >> edge_num >> start_node;

	for (int i = 0; i < edge_num; ++i)
	{
		int a, b, cost;
		cin >> a >> b >> cost;

		vtx[a].push_back({ b, cost });
	}

	dijkstra();

	return 0;
}