아인스트라세의 SW 블로그

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

방금 작성한 포스팅이 1753번 최단경로 문제(다익스트라 기본문제) 였는데, 이 포스팅을 쓰면서 오랜만에 다익스트라 알고리즘을 다시 한번 생각해보게 되었었다.

근데 곧이어 1854번 문제를 풀었는데 그냥 생각나는대로 푸니 되었어서 좀 얼떨떨한 상태이다.

어쨋든 방금 서술한 것과 마찬가지로 1854번 문제도 다익스트라 최단경로 찾기 알고리즘을 사용하는 문제인데, 기본적인 다익스트라 알고리즘은 shortest path므로 가장 짧은 경로를 찾는 알고리즘이다.

그런데 이 문제를 보면 K번째로 짧은 경로를 찾아야 한다.

그래서 아까 포스팅에서 다익스트라 알고리즘을 이야기 하다가 나왔는데, 우선순위 큐에서 가장 먼저 나와서 해당 정점을 처음 방문한 녀석이 가장 짧은 길이라고 서술했었다.

그리고 큐에는 그 정점을 방문할 만한 다른 path 결과도 있지만 처음 나온 녀석이 가장 짧은 경로이기 때문에 그리디 알고리즘이라고도 이야기를 했었다.

그렇다면 두번째로 그 정점을 방문한 녀석은 두번째로 짧은 경로가 될 것이고, 세번째로 방문한 녀석은 세번째로 짧은 경로가 될 것이다.

이러한 방식으로 K번째 방문한 path로 길이를 설정하면 K번째 최단경로를 구할 수 있을 것이다.

다행히 K값이 100으로 작고 N도 1000로 정점수가 그에 맞게 작은 값이다.

이를 이용하여 다익스트라 알고리즘을 변형하면 문제를 쉽게 풀 수 있다.

코드

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

#define INF 2000000000
#define MAXN 1003
#define MAXK 102
vector<pii> edges[MAXN]; //dest, weight
int visit[MAXN];
int dist[MAXK][MAXN]; // [i][j] = i번째 최단경로로 j방문하는 길이
int main() {
	int discovered = 0;
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			dist[j][i] = INF;
		}
	}
	for (int i = 0; i < m; i++) {
		int u, v, w;
		(void)scanf("%d%d%d", &u, &v, &w);
		edges[u].push_back({ v, w });
	}
	priority_queue<pii> pq; // -dist, index
	pq.push({ 0, 1 });
	while (pq.size()) {
		pii cur = pq.top(); pq.pop();
		int distance = -cur.first;
		int current = cur.second;
		if (visit[current] >= k) continue; //k번째 최단경로를 다 구한경우
		int cnt = ++visit[current]; //방문 횟수
		dist[cnt][current] = distance;
		if (cnt == k) discovered++;
		if (discovered == n) break;
		for (pii nx : edges[current]) {
			int next = nx.first;
			int weight = nx.second;
			pq.push({ -dist[cnt][current] - weight, next });
		}
	}
	for (int i = 1; i <= n; i++) {
		if (dist[k][i] == INF) {
			puts("-1");
		}
		else {
			printf("%d\n", dist[k][i]);
		}
	}
	return 0;
}

https://www.acmicpc.net/problem/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;
}

Visual studio 2019에서 프로젝트 생성해서 코딩을 하다가, 디버깅 하지 않고 실행을 눌렀을 때 콘솔이 솨라락 하고 바로 꺼져버리는 경우가 있습니다.

일단 위 매뉴로 갑니다.

좌측 디버깅-일반 가서 쭉 내리면 아래 항목이 있습니다.

저 항목을 체크를 해 줍니다.

콘솔을 닫는다를 체크하는데 왜 되는지는 잘 모르겠네요.