백준 11404 (플로이드) c++ <플로이드-와샬>

문제

11404번: 플로이드

n개의 노드와 m개의 간선 정보가 주어지면 1~n 번 노드 각 노드 기준으로 나머지 노드로 가는 최소비용을 구하면

되는 문제입니다.

단순히 생각하면 1~n 번 각각 다익스트라를 실행해서 구할 수 있습니다.

하지만 플로이드-와샬 알고리즘을 사용하면 좀더 빠르게 구할 수 있습니다.

플로이드-와샬 알고리즘은 모든 정점에대해서 최소비용을 구할 수 있습니다.

다익스트라는 시작점을 기준으로 구하지만 플로이드-와샬은 모두 구할 수 있다는 장점이 있습니다.

 

플로이드-와샬은 이차원 배열을 사용합니다.

arr[1][2] = 1번 노드에서 2번 노드로 가는 최소비용을 저장합니다.

int n;
cin >> n;
for (int i = 1; i <= n; i++) //vertex 테이블 초기화
	for (int j = 1; j <= n; j++)
		arr[i][j] = (i == j ? 0 : INF);

n개의 노드를 입력받습니다. 

정보가 없으면 INF로 저장합니다.

int m;
cin >> m;
for (int i = 0; i < m; i++) {
	int a, b, c;
	cin >> a >> b >> c;
	if (arr[a][b] > c)arr[a][b] = c;
}

m개의 간선정보를 입력받고 배열에 저장합니다.

이때는 일단 어떤 노드를 경유하는 것이 아닌 직접갈 수 있는 비용을 배열에 저장합니다.

void floyd_warshall() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= n; k++)
				if (arr[j][i] != INF && arr[i][k] != INF)
					arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
}

플로이드 와샬 알고리즘 부분입니다.

이 알고리즘의 핵심은 현재 내가 직접갈 수 있는 노드의 비용과 경유해서 가는 비용과 비교해 더 낮은 비용을 고르는 것

입니다.

예를 들어 3번 노드에서 4번 노드로 갈 때는 6이 들지만 1번 노드를 경유해서 가면 7이 듭니다.

이 때 3번 노드에서 4번 노드로 가는 최소비용은 6이 됩니다.

이런식으로 계속해서 반복해 진행합니다.

즉, 시작점은 j, 도착점은 k라고 하고, 경유점은 i라고 했을 때 

점화식은 arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]) 입니다.

---

전체 코드입니다.

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>

#define INF 2000000000
using namespace std;
using ll = long long;
int arr[101][101];
int n;
void floyd_warshall();
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) //vertex 테이블 초기화
		for (int j = 1; j <= n; j++)
			arr[i][j] = (i == j ? 0 : INF);

	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (arr[a][b] > c)arr[a][b] = c;
	}

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

	return 0;
}
void floyd_warshall() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= n; k++)
				if (arr[j][i] != INF && arr[i][k] != INF)
					arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
}