[백준] 11404번: 플로이드 C++ 풀이

접근

이름부터 플로이드 이지만, 단순히 문제만 바라보면,

도시의 가장 빠른 길을 찾는데, 모든 도시를 대상으로 찾아야 한다.

이렇게 모든 대상에 대해서 최단 경로를 구하려면, 플로이드 워셜(Floyd-Warshall) 알고리즘을 이용하면 된다.

그렇지만 나는 이 알고리즘을 제대로 이해하지 못해서 다른 방식으로 해결했다.

 

전략

플로이드 워셜 알고리즘의 전략은

각 정점을 조사해서 해당 정점을 사이로 지나는 두 정점을 찾아서 만약 더 짧은 거리이면  짧은 거리로 갱신한다(두 정점의 직접 경로가 없는 건 ∞ 로 가정)

 

본인은 잘못 이해 해서 시간 복잡도가 조금 더 증가했다.

각 도시 간 거리를 매트릭스의 형태로 저장해서

각 행에 대해서 조사를 하는데, 만약 경로가 있는 도시가 있다면, 그 도시로부터 다른 도시를 또 조사해서 그 도시 까지의 거리를 직접가는 도시를 비교해서 작은 거리로 갱신한다.

그러나 이렇게 하면 전체가 갱신하는 게 안되기 때문에 n번을 반복한다.

n번을 반복하는 이유는  최대 n번이면 모든 경로가 최단 경로로 정해지기 때문이다.

 

구현:

플로이드 워셜 $O(n^3)$

#include <iostream>
#define INF 10000000
using namespace std;
int n,m;
int path[101][101];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m; 
	

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			if (i == j) path[i][j] = 0;
			else path[i][j] = INF;
		}
	}

	for (int i = 0; i < m; i++) {
		int start, end, cost;
		cin >> start >> end >> cost;
		if(path[start][end] > cost)
			path[start][end] = cost;
	}


	for (int i = 1; i <= n; i++) { 
		for (int j = 1; j <= n; j++) {  
				for (int k = 1; k <= n; k++) {

					if (path[k][i] == INF || path[i][j] == INF) continue;

					if (path[k][i] + path[i][j] < path[k][j]) { 
						path[k][j] = path[k][i] + path[i][j];
					}
				}
			
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (path[i][j] == INF) cout << 0 << ' ';
			else cout << path[i][j] << ' ';

		}
		cout << '\n';
	}
	return 0;
}

 

본인 구현 $O(n^4)$

#include <iostream>
#define INF 10000000
using namespace std;
int n,m;
int path[101][101];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m; 
	

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			if (i == j) path[i][j] = 0;
			else path[i][j] = INF;
		}
	}

	for (int i = 0; i < m; i++) {
		int start, end, cost;
		cin >> start >> end >> cost;
		if(path[start][end] > cost)
			path[start][end] = cost;
	}
	
	for (int rep = 0; rep < n; rep++) {
		for (int i = 1; i <= n; i++) { //모든 행 조사
			for (int j = 1; j <= n; j++) { //각 element 조사
				if (path[i][j] < INF && i != j) { //유효한 거리라면
					for (int k = 1; k <= n; k++) { // 그 행 전부 다시 조사
						if (path[j][k] < INF && path[i][j] + path[j][k] < path[i][k]) {
							path[i][k] = path[i][j] + path[j][k];
						}
					}
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (path[i][j] == INF) cout << 0 << ' ';
			else cout << path[i][j] << ' ';

		}
		cout << '\n';
	}
	return 0;
}