[C++] BOJ(백준) 11404 플로이드

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

11404번: 플로이드

 

플로이드 워셜 문제다.

 

모든 지점에서부터 모든 지점까지의 최단 경로를 구하는 문제다.

문제 이름처럼 플로이드 워셜을 이용한다.

 

플로이드 워셜은 코테용이 아닌 이론부터 공부를 했다.

플로이드 워셜의 개념은 아래와 같다.

dij(k)는 i에서 j까지 가는데 k이하의 수를 거쳐서 지나갔을 때의 최단 경로를 의미한다.

거쳐간다의 의미는 i 와 j를 제외한 노드의 번호다.

 

k == 0 일 때는 아무것도 거치지 않기 때문에 처음 가중치와 동일하다.

k == 1 부터는 다른 노드들을 거쳐 지나가는 것이다.

아래와 같은 점화식을 세울 수 있다.

 

해당 식을 수도 코드로 나타내면 아래와 같다.

 

여기서 중요한 점은 k에 대한 반복문이 가장 밖에 있어야 한다.

 

#include <iostream>
using namespace std;

int n, m;
int arr[101][101];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n >> m;

	for (int r = 1; r <= n; r++) 
		for (int c = 1; c <= n; c++) 
			arr[r][c] = 987654321;

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

	for (int i = 1; i <= n; i++) {
		for (int r = 1; r <= n; r++) {
			for (int c = 1; c <= n; c++) {
				arr[r][c] = min(arr[r][c], arr[r][i] + arr[i][c]);
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] == 987654321 || i == j) cout << 0<<" ";
			else cout << arr[i][j] << " ";
		}
		cout << "\n";
	}
}

 

 

사진 출처 : 강의자료