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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 특정 정점에서 다른 정점으로 갈 수 있는 최단거리를 구하는 문제다.

 

모든 정점의 경우를 구해야하기 때문에 플로이드 워셜 알고리즘으로 문제를 풀면 O(N^3)의 시간복잡도로 문제를 해결할 수 있다.

 

문제를 풀기전에 플로이드 워셜 알고리즘을 간단하게 정리하면, 정점 i에서 j로 가는 비용과 정점 i -> k -> j로 가는 비용을 비교해 최단 거리를 갱신하는 과정이다.

 

위의 과정을 3중 for문을 이용하면 모든 정점에서 다른 정점으로 가는 최소비용을 구할 수 있다.

여기서 중요한 점은 경유지 k가 for문의 가장 상위에 있어야 한다.

 

왜 가장 상위에 있어야 하는지 설명하기 전에, 지나갈 수 있는 경유지의 집합을 V라고 가정하자.

 

그러면 DP_V[i][j]는 i에서 j로 갈 때, 지나갈 수 있는 경유지가 V에 있는 원소로 이루어진 최소 비용이다.

 

여기서 DP_V+{k}[i][j] = min(DP_V[i][j], DP_V[i][k] + DP_V[k][j]) 로 표현할 수 있다.

 

즉, 플로이드 워셜 알고리즘이란 경유지 k가 포함된 경우의 최소비용을 k가 포함되지 않은 경우를 이용해 문제를 푸는 DP이기 때문에 k를 가장 상위에 두고 3중 for문으로 쉽게 문제를 해결할 수 있는 것이다.

 

 

​

[아이디어 정리]

1. 플로이드 워셜 알고리즘을 이용해 모든 정점에서 다른 정점으로 가는 최소비용을 구한다.
2. 만약 다른 정점에 갈 수 없다면 0을 출력하고, 갈 수 있다면 최소비용을 출력한다.

 

 

 

Code

 

 

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

const int INF = 10000000;
int main()
{
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int N, M;
	cin >> N >> M;
	vector<vector<int>>graph(N+1, vector<int>(N+1, INF));
	int a, b, c;
	for (int i = 0; i < M; i++) 
	{
		cin >> a >> b >> c;
		graph[a][b] = min(graph[a][b],c);
	}
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			for (int k = 1; k <= N; k++)
				graph[k][j] = min(graph[k][j], graph[i][j] + graph[k][i]);
                
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (graph[i][j] == INF||i==j)
				cout << 0<<" ";
			else
				cout << graph[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

 

---

플로이드 워셜 알고리즘은 DP라는 걸 이해하면 쉽게 느껴지는 알고리즘이지만, 그 전에는 왜 이게 되는지 의문이 많이 들었던 알고리즘인 것 같다.

 

11404번: 플로이드