경로 추적에 대하여 (다익스트라, 플로이드 )

경로를 탐색해나가는 것에 더 나아가, 경로를 저장한 후 출력하라는 문제들이 종종 있다. 

오늘은 어떤 경우에, 어떤식으로 경로를 저장해나가는지 케이스 별로 알아보자

 

1. 다익스트라,벨만포드

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

11779번: 최소비용 구하기 2

백준 문제 11779 번을 풀어보며 알아보자. 이 문제는 다익스트라 문제이지만, 벨만포드도 "경로 추적" 은 동일한

메커니즘으로 돌아간다. 혹시 벨만포드로 된 문제를 풀고 싶다면 1738번 '골목길' 문제를 찾아보도록...

다만 매우 어렵다. 그래도 추후에 이 문제에 대한 해석을 따로 올릴 예정이니 기회가 되면 한번 풀어보면 좋다..! 

 

 

정답 코드

경로찾기를 하기 위한 코드는 [*** (별 세 개) ] 로 표시했다.

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int dist[1010];
int route[1010];

vector<int> ans;
const int inf = 987654321;//무한값
int main() {
	int n, m,a,b,c,st,ed;
	cin >> n >> m;
	for (int i = 0; i < n + 2; i++)
		dist[i] = inf;
	vector<pair<int, int>> path[1000];
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		path[a].push_back({ b,c });
	}
	
	
	cin >> st >> ed;

	priority_queue<pair<int,int>> pq;//비용, 도착지
	pq.push({ 0,st });//st >st 비용은 0
	dist[st] = 0;
	while (!pq.empty()) {
		int cost = -pq.top().first;
		int now = pq.top().second;
		pq.pop();
		
		if (now == ed) {
			break;
		}
		

		//if (dist[now] <= cost)continue;//만약 새로 찾은 경로가 기존경로보다 값이 높다면 스킵.

		//dist[now] = cost;//최단거리 갱신.

		for (auto e : path[now]) {
			int nxt = e.first;
			int nxt_cost = e.second;
			if (dist[nxt]>dist[now]+nxt_cost) {//해당위치 위치로 최단경로 갱신 가능할 시, pq에 넣어 탐색한다. 
				dist[nxt] = dist[now] + nxt_cost;
				route[nxt] = now;//nxt로 가는 최단경로는 직전에 now를 거친다. ***
				pq.push({ -dist[nxt],nxt });

			}
		}
	}
	cout << dist[ed] << endl;
	int idx = ed;//***
	while (idx != st) {//***
		ans.push_back(idx);//***
		idx = route[idx];//***
	}
	ans.push_back(idx);//출발경로도 추가.
	cout << ans.size()<<endl;
	for (int i = ans.size()-1; i >= 0; i--) {//도착지>출발지 경로를 저장했으므로 
		cout << ans[i] << " ";         //거꾸로 출력해 출발> 도착지의 경로를 출력한다.
	}
	
	cout << endl;
}

 

위 코드 중 ***표시된  route[nxt]=now; 라인을 살펴보자.

주석에 달아놓았듯이, nxt 의 위치로 가는데 now를 거치는 것이 최단경로일 때, 그 사실을 저장해주는 것이다.

(nxt로 가려면 now를 직전에 거쳐가야한다는것.)

따라서 route[x]= y;  의 의미는 >> 출발지 st에서 x로 가려면 y번 을 직전에 거쳐야한다는 뜻이다.

우리는 이를 통해 완벽한 경로를 찾기 위해, 도착지부터 경로를 거슬러 올라간다.

도착지> 도착지로 가기 '바로직전' 에 거치는 도시 > 그 직전에 거치는 도시> 그직전>............

> 출발지.

아래 idx=ed; 쪽부터 별표된 코드들을 쭉 봐 보자. 

우리는 idx에 경로로 거치는 도시들을 갱신하며, ans 벡터에 추가해준다. 

ans 벡터는 결국

도착지, 직전 도시,......출발지       

이런식으로 값을 저장할 것이고, 출발지 > 도착지의 경로를 올바르게 출력하기 위해,

이 벡터를 거꾸로 출력해주면 경로 추적이 끝난다. 

 

 

 

2.플로이드 와샬

> 11780번 문제를 살펴보자! 위에서 나온 문제와 매우 비슷하지만, 다익스트라, 플로이드를 언제 사용해야되는지

안다면, 이 문제는 플로이드로 풀어야한다는걸 쉽게 캐치 할 수있을 것이다. 아직 최단거리 문제에서 어떤 방식을

사용해야 하는 지 감이 오지 않는다면 

https://codenme.tistory.com/6?category=1026697 

최단거리류 알고리즘에 대해서(다익스트라,벨만포드,플로이드 등등)

위 링크를 들어가서 공부하고 오자!

 

정답 코드

#include<iostream>
#include<vector>
using namespace std;
int arr[101][101];
const int inf = 987654321;


//한정점에서 다른정점으로 가는데 드는 최단거리가 각 배열에 저장되있다.


int nxt[101][101];//[a][b] a>b까지최단거리로 가려면 어디를 거쳐가야하는가. (바로다음번에)
int main() {
	int n, m, a, b, c;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			arr[i][j] = inf;
		arr[i][i] = 0;//스스는 도착가능.
	}
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		if (arr[a][b]>c) {//중요!
			arr[a][b] = c;
			nxt[a][b] = b;//1개짜리 간선도 nxt작업필요.
		}
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				int use = arr[i][k] + arr[k][j];
				if (arr[i][j] > use) {
					arr[i][j] = use;
					nxt[i][j] = nxt[i][k];//k거쳐가는게 최단. ***
				}

			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] != inf)
				cout << arr[i][j] << " ";
			else
				cout << 0 << " ";
		}
		cout << endl;
	}
	
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] == inf||arr[i][j]==0)
				cout << "0" << endl;
			else {
				//***아래부터 경로 추적
				vector<int> path;
				path.push_back(i);
				while (path.back() != j) {
					int now = path.back();
					path.push_back(nxt[now][j]);//출발지를 한칸씩 도착지 쪽으로 당긴다고 생각해도됨.
				}
				cout << path.size() << " ";
				for (auto p : path)
					cout << p << " ";
				cout << endl;
				
				
				


			}
		}
	}
	


}

 

 

첫 ***이 적혀있는 줄을 보자.

k를 거치는 것이 최단경로라고 갱신해줄 때, 이를

nxt[i][j]=k; 로 표기했다.    (i>j 경로는 k를 거쳐야 최단경로) 

 

여기서 다익스트라와 다른 부분은, 다익스트라는 도착지에서부터 서서히 출발지 쪽으로 당기면서 탐색을

해나갔다면, 이 코드에선 출발지를 서서히 도착지 쪽으로 당겨나가며 경로를 찾아나간다는 것이다. 

이는 다익스트라는 도착지의 정보만 우선순위 큐에 저장하며 탐색해나가는 반면, 플로이드와샬은 

출발지, 도착지 정보를 모두 가지고 탐색에 임하기에 출발지 부터 경로를 탐색하는 것이 가능한 것이다.

(물론 다익스트라 처럼 도착지 부터 탐색 역시 가능하나, 굳이 출력 배열을 뒤집는 번거로움을 감수할 필요는 없기에 출발> 도착의 방향으로 경로를 찾아나간 것)