백준 1753번 문제 '최단경로' 풀이

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

1753번: 최단경로

 

백준 1753번 문제, 최단경로 풀이입니다.

 

이 문제는 알고리즘 공부하는 커리큘럼의 예제 문제같은 문제로, 딱 이거 쓰면 됩니다~ 이런 문제이죠.

 

방향 그래프에서, 시작점 하나의 점에서 모든 점으로 가는 최단경로를 모조리 구하는 그러한 문제입니다.

 

가중치가 10이하 자연수라는 제약 조건이 있고, 최대 2만개의 정점과 30만개의 간선이 있을 수 있습니다.

 

정점이 모두 양수이고, 한 점에서 시작하는 모든 최단경로를 구하는 문제는 다익스트라의 최단경로 알고리즘을 이용해서 풀이를 할 수 있습니다.

 

따라서 다익스트라 최단경로 알고리즘을 정확하게 구현하면 됩니다.

 

물론 실수가 있게 구현하면 시간초과가 나던지 오답이 나던지 할 수 있지요.

 

다익스트라 최단경로 알고리즘

다익스트라 알고리즘은 BFS와 유사한점이 꽤 있습니다.

코드 형태도 비슷한 점이 꽤 있지요.

 

간단하게 생각하면 BFS는 큐를 쓰고, 다익스트라는 우선순위 큐를 씁니다.

BFS는 모든 간선의 가중치가 같은 경우 사용할 수 있고, 다익스트라는 모든 간선의 가중치가 양수인 경우 사용할 수 있지요.

 

그리고 다익스트라는 조금 다른 점이 그리디한 알고리즘이라는 것입니다.

그리고 우선순위 큐에는 지금까지 방문한 모든 정점에 이웃한 정점의 정보가 들어있습니다. 

 

이 우선순위 큐는 바로 다음 Step에 방문할수 있는 정점들이 모여잇는데, 그 중에서 Total 합쳐서 이동 거리가 가장 짧은 녀석 먼저 방문하는 방식입니다.

 

따라서 최소값이 우선순위가 높은 우선순위 큐를 만들어야 하지요.

 

그래서 큐에 있는 일부 값들은 세상의 빛을 보기 전에, 모든 연결된 정점을 다 방문하게 되어 영영 나오지 못하게 되는 경우도 있습니다. 그런녀석들은 최단 경로를 만드는데 도움이 되지 않는 녀석들이죠.

 

그래서 특정 정점을 가장 먼저 방문한 경우, 큐에 있는 녀석들은 그 이미 방문한 값 보다 더 짧은 거리에 방문할 일은 없습니다.

 

그래서 한번만 방문하면 되지요.

 

구현전략

여기서 Vertex수가 2만이므로, 인접 행렬을 구성할 수는 없습니다. 메모리가 너무 많이 들기 때문이지요.

 

인접 행렬은 노드수의 제곱만큼의 메모리를 사용하는데 그러면 메모리 초과가 납니다.

 

따라서 인접 리스트를 이용해서 구현합니다.

 

C++ STL에 있는 Pair를 사용할 것이고, Pair는 비교 연산이 first를 먼저 비교하고, first가 같은 경우 second의 대소 비교를 합니다.

 

C++ STL에 있는 Priority_queue는 기본적으로 MAX_HEAP 형태이므로, -를 넣어서 음수 값을 넣는 방식으로 최소값이 먼저 나오게 만들어서 구현하도록 합니다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

#define INF 2000000000
#define MAXN 20004
vector<pii> edges[MAXN]; //dest, weight
bool visit[MAXN];
int dist[MAXN];
int main() {
	int discovered = 0;
	int V, E, K;
	scanf("%d%d%d", &V, &E, &K);
	for (int i = 0; i <= V; i++) {
		dist[i] = INF;
	}
	for (int i = 0; i < E; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		edges[u].push_back({ v, w });
	}
	priority_queue<pii> pq; // -dist, index
	pq.push({ 0, K });
	while (pq.size()) {
		pii cur = pq.top(); pq.pop();
		int distance = -cur.first;
		int current = cur.second;
		if (visit[current]) continue;
		if (dist[current] == INF) discovered++;
		visit[current] = true;
		dist[current] = distance;
		if (discovered == V) break;
		for (pii nx : edges[current]) {
			int next = nx.first;
			int weight = nx.second;
			pq.push({ -dist[current] - weight, next });
		}
	}
	for (int i = 1; i <= V; i++) {
		if (dist[i] == INF) {
			puts("INF");
		}
		else {
			printf("%d\n", dist[i]);
		}
	}
	return 0;
}