101. 플로이드 워샬 알고리 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★☆☆

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, a, b, c;
	cin >> n >> m;
	
	vector<vector<int>> dis(n+1, vector<int>(n+1, 5000));
	
	for(int i = 1; i <= n; i++)
	{
		dis[i][i] = 0;
	}
	
	for(int i = 1; i <= m; i++)
	{
		cin >> a >> b >> c;
		dis[a][b] = c;
	}
	
	for(int k = 1; k <= n; k++)
	{
		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= n; j++)
			{
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			if(dis[i][j] == 5000)
				cout << "M ";
			else
				cout << dis[i][j] << " ";
		}
		cout << "\n";
	}
	
	return 0;
}

1. 플로이드 워샬 알고리즘은 최소비용 거리를 구할 때 사용하는데, 특히 2차원 배열을 사용해야할 때 매우 유용하다. 다익스트라 알고리즘보다 훨씬 코드가 깔끔하므로 자주 쓰도록 하자.

 

2. 간단하게 말하면 dis[i][j] 를 노드 i에서 j로 가는 비용이라고 하자. 이 때 i에서 j로 가는 방법은 매우 다양하다.

• 한 번에 i -> j 로 가기
• i -> k, k -> j 로 k를 경유해서 가기
• i -> k, k -> z, z -> j로 k, z를 경유해서 가기

등등이 있다. 이를 활용할 것이다.

 

3. 위 3중 for문에서 k의 의미가 바로 경유해서 갈 노드의 번호를 의미한다. k가 1~5까지 돈다. 1~5까지의 노드가 k번 노드를 경유해서 가는 비용이 2차원 벡터 dis의 값으로 들어간다. 모든 루트의 비용을 계산해서 최소비용이 결국 남게된다.