[BOJ] 11404 : 플로이드 (C++) with 플로이드

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

11404번: 플로이드

걸린 시간 : 12분 50초 (이에 해당하는 강의를 본 직후 풀어서 시간은 의미 없음)

---

플로이드 와샬 알고리즘의 가장 기본이 되는 문제이다.

플로이드 알고리즘은 임의의 점부터 임의의 점까지의 모든 최단거리를 알고 싶을 때 사용하는 O(N^3) 알고리즘이다. N이 몇백 수준일 때 사용하면 된다. 1000이 넘어가는 시점부터는 다익스트라 등 다른 알고리즘을 사용할 수 있는지 확인하자.

알고리즘

플로이드 알고리즘은 생각해내긴 어렵지만 구현하기는 너무 쉬운 알고리즘이다. 왜 그렇게 되는지는 직접 랜덤한 그래프를 그려보고, 실제 코드를 따라 해보면 단번에 이해가 갈 것이다.

그래프를 인접행렬의 형태로 dist 라는 배열에 넣는다. 초기화는 평소와 같이 해준다. (경로가 없을 땐 INF, 자기 자신일 땐 0)

이제 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 라는 식을 3중 for문을 통해 실행하면 된다. 현재 값과 다른 지점을 거쳐갈 때 중 작은 값으로 최신화해주는 것이다. for문의 순서는 k → i → j 이다.

정답코드

#include <bits/stdc++.h>
 
using namespace std;
 
int n, m;
int dist[101][101];
 
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < 101; i++)
		fill(dist[i], dist[i]+101, 987654321);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		dist[a][b] = min(dist[a][b], c);
	}
	for (int i = 1; i <= n; i++)
		dist[i][i] = 0;
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dist[i][j] == 987654321)
				cout << "0 ";
			else
				cout << dist[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}