백준 1753 - 최단경로

문제링크

• 백준 1753

문제설명

• 방향 그래프가 주어질 때 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하라.
• 정점의 개수는 2만개, 간선의 개수는 30만개로 시간초과와 메모리초과에 유의해야 한다.

문제접근

• 문제에서 주어지는 최대 정점의 개수, 간선의 개수를 고려했을 때 인접행렬을 사용하는 경우 메모리 초과에 걸린다. 따라서, 인접리스트를 이용해 최대 30만개의 데이터만 담을 수 있도록 한다.
• 최단경로 알고리즘은 여러가지가 있지만, 이 문제의 경우 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리 를 구하는 알고리즘이므로 다익스트라 알고리즘 이 적절한 방법이다.
• 로직은 다음과 같다.
• 인접리스트 형태로 그래프 정보를 담는 테이블을 만든다.
  • vector<pair<int, int» table[u] 의 형태를 가지며, v -> table[u][i].first, w -> table[u][i].second 를 의미한다. 즉, u->v 로 가는 가중치 w를 입력으로 들어온 순서대로 담는다.
• 처음 모든 노드로의 최단 거리는 INF 로 설정한다.
• 시작점의 최단 거리는 0 이다.
• 우선순위 큐로 최소 힙을 구성하여 노드를 이동할 때 비용이 최소인 노드들부터 선택할 수 있도록 한다.
  • 우선순위 큐에서 pair<int, int> 를 사용하는 경우 첫번째 인자를 정렬의 우선순위로 본다.
  • 비용이 작은 순서대로 방문하기 때문에 기존에 방문하는데 필요한 비용보다 특정한 노드를 거쳐서 방문하는 비용이 더 큰 경우는 다른 경로를 탐색할 필요가 없다.
• 특정 노드를 통해 목표 노드를 방문했을 때, 이전에 필요했던 비용보다 적다면 최소 비용을 갱신한다.

구현

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

#define INF 9e8
using namespace std;

vector<pair<int, int>> table[20001];
// 우선순위 큐는 첫번째 인자를 우선적으로 비교하여 정렬함
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int dist[20001];
int V, E;

void dijkstra(int start) {
	pq.push(make_pair(0, start)); // (w, v) 순서로 올 것
	dist[start] = 0;

	while (!pq.empty()) {
		int u = pq.top().second;
		int w = pq.top().first;
		pq.pop();

		for (int i = 0; i < table[u].size(); i++) {
			int v = table[u][i].first;
			int x = table[u][i].second;
			if (dist[v] > w + x) {
				dist[v] = w + x;
				pq.push(make_pair(w+x, v));
			}
		}
	}
}

int main()
{
	int K;
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d", &V, &E);
	scanf("%d", &K);

	int u, v, w;
	for (int i = 0; i < E; i++) {
		scanf("%d %d %d", &u, &v, &w);
		table[u].push_back(make_pair(v, w));
	}

	// init
	for (int v = 1; v <= V; v++) {
		dist[v] = INF;
	}
	dijkstra(K);
	for (int v = 1; v <= V; v++) {
		if (dist[v] == INF) printf("INF\n");
		else printf("%d\n", dist[v]);
	}
}