[알고리즘] 백준 11404번: 플로이드 (C++), 플로이드 와샬

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

11404번: 플로이드

 

최단 경로를 구하는 알고리즘 두 번째, 플로이드 와샬(Floyd Warshall)이다.

나동빈 님의 블로그(https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https:%2F%2Fwww.google.com%2F)를 통해 공부했고, 나동빈 님의 글을 토대로 정리하는 글이다.

 

[플로이드 와샬 정리]

1) DP의 형식으로 최단 경로를 갱신한다. (DP라고 해서 어렵지 않다. 오히려 간단한 코드 형식이다.)

 

2) 거쳐가는 노드를 기준으로 최단 경로를 갱신한다.

>> 플로이드 와샬의 핵심이다.

// k = 거쳐가는 노드
for (int k = 1; k <= n; k++) {
	// i = 시작 노드
	for (int i = 1; i <= n; i++) {
		// j = 도착 노드
		for (int j = 1; j <= n; j++) {
			if (cache[i][k] != INF && cache[k][j] != INF) {
				cache[i][j] = min(cache[i][j], cache[i][k] + cache[k][j]);
			}
		}
	}
}

3) 자기 자신에게 가는 경로가 0으로 계산되지 않는다.

>> 코드 구성으로 인해 자기 자신으로 가는 경로 또한 무조건 다른 노드를 거쳐서 들어오기 때문에 플로이드 와샬이 끝나고, 자기 자신으로 가는 경로는 0으로 바꿔주어야 한다.

 

4) 시간 복잡도는 O(n^3)이다. 2번의 코드를 보면 이해가 된다.

---

[문제]

문제로 들어가 보자. 간선을 입력할 때, 훼이크가 있었다. 간선을 입력하는 대로 거리를 그래프에 입력해줬는데 "1 4 1" 간선이 입력된 후에 "1 4 2"가 입력되는 경우가 있었다.

>> 입력할 때 해당 간선의 현재 간선보다 작은 경우에 할당해주었다.

// 간선 입력
for (int i = 0; i < m; i++) {
	int a, b, c;
	cin >> a >> b >> c;
	if (c < graph[a][b]) {
		graph[a][b] = c;
	}
}

 

그리고 플로이드 와샬의 코드에서

if (cache[i][k] != INF && cache[k][j] != INF) {
	cache[i][j] = min(cache[i][j], cache[i][k] + cache[k][j]);
}

해당 조건을 걸어주지 않아도 답이 나오지만 해당 조건을 걸어준 이유는

저 조건의 의미는 i->k, k->j로 가는 간선이 존재할 때라는 의미이다. 당연히 문제를 풀어갈 때는 의미가 없는 조건이지만 플로이드 와샬이라는 알고리즘의 의미에서는 필요한 조건이다.

 

---

[AC 코드]

#include <iostream>
#include <cmath>
#define MAX 100 + 1
#define INF 987654321
using namespace std;

int cache[MAX][MAX];
int graph[MAX][MAX];
int n, m;

void floydWarshall() {
	// 최단 거리 (결과 그래프) 초기화
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cache[i][j] = graph[i][j];
		}
	}

	// k = 거쳐가는 노드
	for (int k = 1; k <= n; k++) {
		// i = 시작 노드
		for (int i = 1; i <= n; i++) {
			// j = 도착 노드
			for (int j = 1; j <= n; j++) {
					cache[i][j] = min(cache[i][j], cache[i][k] + cache[k][j]);
				
			}
		}
	}
}

int main() {
	cin >> n >> m;

	// 그래프 초기화
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			graph[i][j] = INF;
		}
	}
	
	// 간선 입력
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (c < graph[a][b]) {
			graph[a][b] = c;
		}
	}

	floydWarshall();

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j || cache[i][j] == INF) {
				// i == j인 경우까지 0으로
				cout << 0 << ' ';
			}
			else {
				cout << cache[i][j] << ' ';
			}
		}
		cout << '\n';
	}
	return 0;
}