BOJ - 11404번 플로이드(C++)

문제 출처: https://www.acmicpc.net/problem/11404

문제 난이도

Gold 4

문제 접근법

기본 알고리즘 중
플로이드-와샬 알고리즘(음의 사이클이 없는 그래프에 대해서 모든 정점 사이의 최단거리를 구하는 것이 가능)을 이용하는 문제다.
다익스트라처럼 모든 정점에 대한 거리를 계산할 수 있다.
하지만 플로이드는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것이다.

그래서 삼중 포문으로 중간 정점의 수를 계속 갱신해가며 최단 거리를 구한다. 그렇다보니 노드 값 범위가 클수록 계산하는데 시간이 걸린다는 것을 유념하자.(O(N^3))
노드와 노드 사이의 경로 값이 없을 때 INF 값을 넣어주는데, 이 때 자기 자신의 노드 경로(i==j)는 빼주고 INF를 넣어야한다.

플로이드-워셜 알고리즘은 거의 대부분이나 모든 꼭짓점 쌍이 변으로 연결된 밀집 그래프에서 모든 꼭짓점 쌍 간의 경로를 계산할 때 적합하다.

통과 코드

#include <iostream>
#include <algorithm>

using namespace std;

int dy[101][101];


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m;
	int INF = 987654321;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (dy[a][b] != 0) {
			dy[a][b] = min(dy[a][b], c);
		}
		else dy[a][b] = c;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if(i != j && dy[i][j] == 0) dy[i][j] = INF;
		}
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (dy[i][k] != INF && dy[k][j] != INF) {
					dy[i][j] = min(dy[i][k] + dy[k][j], dy[i][j]);
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dy[i][j] == INF) dy[i][j] = 0;
			cout << dy[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}