[백준/C++] 플로이드 2

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 플로이드 워셜 알고리즘 문제에 경로를 역추적 하는 게 추가된 문제다.

이전에 풀었던 플로이드문제

 

 

모든 경로에 대해 구해야 하므로 플로이드 워셜 알고리즘을 이용하면 O(n^3)으로 구할 수 있다.

 

플로이드 워셜 알고리즘이란 쉽게 말해 몇 번의 경로를 거쳐서 가는게 최소 비용이 되는지 구하는 방법으로 n개의 노드가 있을 때, [i][j]로 가는 최소 경로를 구하는 방법은 그 사이에 포함 될 수 있는 모든 노드의 수 만큼 k를 반복하면 되는 방법이다.

(즉, [i][j] = [i][k]+[k][j]에서 k는 중간에 거치는 노드의 수 이므로 n만큼 반복하면 모든 노드에 대한 최소 비용을 구한다)

 

이 때, 경로의 역추적은 [i][j]로 가는 최소 비용이 [i][k]+[k][j]를 거쳐서 가는 경로라면 [i][k]의 경로에 [k][j]의 경로를 합친 경로를 [i][j]에 저장해 문제를 해결했다. 

 

 

+ 단순히 경로를 저장했는데, 다른 방법도 있다.

이전에 어떤 위치에서 출발했는지 [i][j]에 저장하는 방법이다.

예를 들어 a, b, c, d, e의 경로를 거치는게 최소 비용이라고 생각해보자.

그러면 [a][e]에는 d를 저장, [a][d]에는 c를 저장하면서 나머지도 마찬가지로 진행한다.

즉, [st][ed]에서 항상 ed에는 바로 직전에 거쳤던 노드를 저장하는 방법이다. 그러면 ed를 감소시키는 것으로 모든 경로를 역 추적 할 수 있다.

 

 

 

 

​

[아이디어 정리]

1. 플로이드 워셜 알고리즘으로 모든 경로에 대한 최소 비용을 구한다.
2. 이동했던 경로는 [i][j]에 대한 경로가 바뀔 때 마다 갱신한다. 이 때, 경로를 직접 저장하거나, 바로 직전에 어떤 노드에서 왔는지를 이용해 저장한다.
3. 경로를 역 추적해 출력한다.

 

Code1 (직접 저장)

 

 

#include <iostream>
#include <vector>

using namespace std;

const int INF= 1000000000;
struct CR {
	int cost;
	vector<int> root;
};

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int n,m;
	cin >> n;
	cin >> m;
	CR def;
	def.cost = INF;
	vector<vector<CR>> graph(n + 1, vector<CR>(n+1,def));
	int a, b, c;
	vector<int> tmp(2, 0);
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		graph[a][b].cost = min(graph[a][b].cost,c);
		tmp[0] = a, tmp[1] = b;
		graph[a][b].root = tmp;
	}
	for (int i = 1; i <= n; i++) {
		graph[i][i].cost = 0;
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (graph[i][j].cost > graph[i][k].cost + graph[k][j].cost)
				{
					graph[i][j].cost = graph[i][k].cost + graph[k][j].cost;
					vector<int> nv(graph[i][k].root.begin(), graph[i][k].root.end() - 1);
					nv.insert(nv.end(), graph[k][j].root.begin(), graph[k][j].root.end());
					graph[i][j].root = nv;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (graph[i][j].cost == INF) {
				cout << "0 ";
			}
			else {
				cout << graph[i][j].cost << " ";
			}
		}
		cout << "\n";
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (graph[i][j].root.size() < 1) {
				cout << 0 << "\n";
			}
			else {
				cout << graph[i][j].root.size() << " ";
				for (int k = 0; k < graph[i][j].root.size(); k++) {
					cout << graph[i][j].root[k] << " ";
				}
				cout << "\n";
			}
		}
	}

	return 0;
}

Code1 (바로 직전에 방문한 노드를 저장)

 

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int INF= 1000000000;
struct CR {
	int cost;
	int pre;
};

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int n,m;
	cin >> n;
	cin >> m;
	CR def;
	def.cost = INF;
	vector<vector<CR>> graph(n + 1, vector<CR>(n+1,def));
	int a, b, c;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		graph[a][b].cost = min(graph[a][b].cost,c);
		graph[a][b].pre = a;
	}
	for (int i = 1; i <= n; i++) {
		graph[i][i].cost = 0;
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (graph[i][j].cost > graph[i][k].cost + graph[k][j].cost)
				{
					graph[i][j].cost = graph[i][k].cost + graph[k][j].cost;
					graph[i][j].pre = graph[k][j].pre;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (graph[i][j].cost == INF) {
				cout << "0 ";
			}
			else {
				cout << graph[i][j].cost << " ";
			}
		}
		cout << "\n";
	}
	for (int i = 1; i <= n; i++) 
	{
		for (int j = 1; j <= n; j++) 
		{
			if (graph[i][j].cost!=INF&&graph[i][j].cost!=0)
			{
				int now = graph[i][j].pre;
				stack<int> st;
				st.push(j);
				while (now != i)
				{
					st.push(now);
					now = graph[i][now].pre;
				}
				cout << st.size() + 1 << " "<<i<<" ";
				while (!st.empty())
				{
					cout << st.top()<<" ";
					st.pop();
				}
				cout << "\n";
			}
			else 
			{
				cout << 0 << "\n";
			}
		}
	}

	return 0;
}

---

문제는 빨리 풀었는데, 중간에 방문할 수 없는 경로에 대해 비용을 0으로 만들어주는 것을 깜빡해서 오답이 났다.

실제로 문제 풀 때는 이러지 않았으면...

 

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