백준 11404 플로이드 C++

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

 

풀이

플로이드-워셜 알고리즘을 이용한다.

 

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다.
시간복잡도는 O(V^3)이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이다. 

 

설명

플로이드-워셜 알고리즘은 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용한다.

조금 더 구체적인 설명을 위해, 임의의 노드 s 부터 e 까지 가는데 걸리는 최단거리를 d[s][e]라고 하자. (처음에 d[s][e]의 값은 노드 s와 노드 e가 직접적으로 연결되어 있다면 그 노드의 가중치만큼, 그렇지 않다면 무한(INF)로 초기화한다.)

이 d[s][e]를 구하기 위해서, s와 e 사이의 모든 노드 m에 대해, 현재 d[s][e]에 저장되어 있는 값과, d[s][m]+d[m][e]의 값을 비교한다. 이 때 d[s][m]+d[m][e]의 값이 현재의 d[s][e] 값보다 작으면, d[s][e]를 d[s][m]+d[m][e] 의 값으로 업데이트한다.

 

출처: 나무위키 플루이드-워셜 알고리즘 참고

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define INF 987654321
#define MAX 101
int n, m;
int graph[MAX][MAX];

void Floyd_Warshall() {
	for (int i = 1; i <= n; i++) { // i vertex
		for (int j = 1; j <= n; j++) { //from vertex
			for (int k = 1; k <= n; k++) { //to vertex
				if (graph[j][i] != INF && graph[i][k] != INF) {
					graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k]);
				}
			}
		}
	}
}

int main() {
	cin >> n;
	cin >> 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;
		graph[a][b] = min(graph[a][b], c);
		
	}
	//플로이드-워셜 알고리즘
	Floyd_Warshall();
	//출력
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if ((i == j) || (graph[i][j] == INF)) {
				cout << 0 << " ";
			}
			else {
				cout << graph[i][j] << " ";
			}
		}
		cout << '\n';
	}
	return 0;
}