[백준 BOJ/C++] 5719 거의 최단 경로

5719번: 거의 최단 경로

다익스트라 알고리즘을 통해 최단 경로를 찾아내는 전형적인 문제에서 살짝 꼬아서 난이도를 높인 문제다.
문제 이름에서 유추할 수 있듯 최단 경로를 제외한 그 다음 최단 경로를 찾아 그 길이를 출력해야 한다.

 

 

예를 들어 아래 그림과 같은 입력이 주어졌을 때 굵은 화살표로 표시된 최단 경로가 아니라 점선으로 표시된 그 다음 최단 경로를 찾아야 한다.
주어진 예제와 같이 최단 경로는 여러개일 수 있으며 이 경우 모든 최단 경로가 제외되어야 한다.

 

출처 - Baekjoon Online Judge

 

 

---

 

 

문제의 포인트

1. 주어진 입력을 어떻게 그래프로 표현할 것인가?
2. 최단 경로를 어떻게 찾고 어떻게 제외시킬 것인가?

 

 

그래프의 표현

입력은 다른 일반적인 그래프 문제와 같이 간선의 정보로 주어진다.
각 간선은 단방향이고 길이라는 가중치를 가지고 있다.
간선 정보가 주어졌을 때 그래프를 자료구조로 표현하는 방법에는 인접 행렬 (adjacency matrix)과 인접 리스트 (adjacency list)가 있다.

 

 

인접 행렬은 직관적이기 때문에 사용하기 쉽고 필요한 경우 update도 간단하다는 장점이 있지만 전체 Node 수의 제곱 만큼의 배열을 잡아두고 사용하기에 메모리 제한에 걸릴 가능성이 있다.

 

 

인접 리스트는 C언어가 아니라면 구현에 불필요한 시간과 에너지를 투입하지는 않지만 표현 자체가 직관적이지 않기 때문에 debugging이나 구현 중 확인, update가 간단하지는 않고 익숙해질 필요가 있다.
하지만 Node 수가 많은 문제의 경우 필수로 사용해야 할 수 있다.

 

 

이 문제는 Node 수가 최대 500개로 적은편이고 간선 정보를 제거할 필요가 있어 인접 행렬로 구현해봤다.

 

 

최단경로 탐색과 제거

최단 경로는 dijkstra algorithm 을 이용해서 간단히 구할 수 있다.
하지만 이 문제는 그 다음 최단 거리를 구해야 하는 문제다.

 

 

최대한 적은 탐색으로 거의 최단 경로를 찾아내는 방법을 고민했지만 마땅한 방법은 없어보였고 간선의 수도 최대 10000개로 적은 편이라서 다시 탐색하는 방법으로 풀어보았다.
여러개일 수 있는 최단경로에 해당하는 간선들을 모두 제거하고 그 상태에서 다시 최단경로를 구하는 방식으로 접근했다.

 

 

1. dijkstra 로 최단 경로 찾기
2. 최단 경로에 포함되는 간선 제거
3. dijkstra로 최단 경로 찾기

 

 

문제는 "어떤 방법으로 최단 경로에 포함되는 간선들을 제거할것인가" 였다.
첫 다익스트라를 끝내기 전까지는 최단 경로를 알지 못하기 때문에 어쨌든 결국 다 돌고 나서 거꾸로 최단 경로를 확인 하는 방법 밖에는 없을것 같았다.

 

 

우선 시작지점에서 각 Node까지의 최단 거리를 배열에 기록해두고 끝 지점에서부터 거꾸로 왔을것 같은 길을 탐색해가면 최단 경로를 지울 수 있다.

 

 

예를 들어 마지막 Node가 6번, 최단거리가 4라고 한다면 6번으로 올 수 있는 바로 앞 Node인 'x'에 대해
('x'까지의 최단 거리) + ('x' -> 6번 간선의 거리) == 4 인지 확인해나가는 방식이다.
이것을 dist 배열을 이용해 거꾸로 BFS 를 돌려 찾아가는 방식으로 구현했다.

 

---

 

전체 Code

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

#define INF 987654321
using namespace std;

int N, M;
int S, D;

int adj[500 + 10][500 + 10];
int dist[500 + 10];

int rqueue[500 + 10];
int wp, rp;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
void initDist() {
	int i;

	for (i = 0; i < N; i++)
		dist[i] = INF;
}

void initAdj() {
	int i, j;

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			adj[i][j] = 0;
		}
	}
}

void dijkstra() {
	int curr, curr_p, next, next_p, i;

	pq.push({ S, 0 });
	dist[S] = 0;

	while (!pq.empty()) {
		curr = pq.top().first;
		curr_p = pq.top().second;
		pq.pop();

		if (curr == D) {
			continue;
		}

		for (i = 0; i < N; i++) {
			if (adj[curr][i] <= 0) continue;

			next = i;
			next_p = curr_p + adj[curr][next];
			
			if (next_p >= dist[next]) continue;
			
			pq.push({ next, next_p });
			dist[next] = next_p;
		}
	}
}

void BFS() {
	int i, j, curr;

	rqueue[wp++] = D;

	while (wp > rp) {
		curr = rqueue[rp++];
		if (curr == S)
			continue;

		for (i = 0; i < N; i++) {
			if (adj[i][curr] == 0) continue;
			if (adj[i][curr] + dist[i] == dist[curr]) {
				rqueue[wp++] = i;
				adj[i][curr] = 0;
			}
		}
	}
}

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	int i, u, v, p;

	while (1) {
		initAdj();
		cin >> N >> M;
		if (N == 0 && M == 0)
			break;

		cin >> S >> D;

		for (i = 0; i < M; i++) {
			cin >> u >> v >> p;
			adj[u][v] = p;
		}
		initDist();
		dijkstra();		

		BFS();

		initDist();
		dijkstra();

		if (dist[D] >= INF)
			cout << "-1\n";
		else
			cout << dist[D] << "\n";
	}
	
	return 0;
}