[알고리즘] 백준 11404번: 플로이드 (C++), 플로이드 와샬
https://www.acmicpc.net/problem/11404
11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
최단 경로를 구하는 알고리즘 두 번째, 플로이드 와샬(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;
}