[백준 11404] 플로이드

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

---

해설

문제의 제목을 보면 아시겠지만, 플로이드 와샬 알고리즘을 사용하는 문제입니다.

플로이드 와샬은 하나의 정점에서 출발해서 다른 정점으로부터의 최단 거리를 구하는 다익스트라 알고리즘과 달리 모든 정점에서 모든 정점으로의 최단 거리를 구할 때 사용됩니다.

---

플로이드 원리

 

플로이드의 원리라고 하면, 일단 1번, 2번, 3번 총 세개의 정점이 있다고 가정해봅시다.

 

i) 1번에서 3번을 가는 데, 15원

ii) 1번에서 2번을 가는 데, 5원

iii) 2번에서 3번을 가는 데, 2원

 

여기서 우리는 1번 정점에서 3번 정점을 가기로 결정하고, 첫번째 만약 i번 방식으로 1번에서 바로 3번으로 간다면 15원이 들 것입니다.

하지만, 우리는 ii번 방식과 iii번 방식을 이용 해 1번을 거쳐 2번을 거쳐 3번으로 도달하게 된다면

5원 + 2원으로 총 7원이 들게 될 것입니다.

 

여기서 최단 거리는 i)+ii) 인 1-> 2-> 3 이겠죠!

 

그래서 우리는 새로운 결론을 도출할 수있습니다.

 

플로이드는 중간에 점들을 끼워서 최단 거리를 구해주는 구나!

 

	for(int k=0; k<n; k++)
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

(플로이드 점화식)

 

따라서 11404번 플로이드 문제는 플로이드 와샬의 기본 문제이므로 위 점화식을 잘 이용하면 문제가 풀리게 됩니다.

---

소스 코드

 

 

#include <iostream>
using namespace std;
int dp[101][101];
const int INF = 1e9;

int main(){
	int n, m; cin >> n >> m;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++)
			dp[i][j] = INF;
		dp[i][i] = 0;
	}
	
	for(int i=0; i<m; i++){
		int u, v, w; cin >> u >> v >> w;
		u--; v--;
		dp[u][v] = min(dp[u][v], w);
	}
	
	for(int k=0; k<n; k++)
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
	
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(dp[i][j] == INF) cout << 0 << ' ';
			else cout << dp[i][j] << ' ';
		}
		cout << '\n';
	}	
}