[Baekjoon] 11404번: 플로이드

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

11404번: 플로이드

 

---

 

문제 해결 과정

착안

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)에 따라 문제에서 요구하는 도시 간 거리를 계산하고자 하였다. 음수 가중치 간선이 없기 때문에 일반적인 방법으로 문제를 해결하고자 하였다.

 

구현

알고리즘을 구현함에 있어서, 삼중 반복문의 루프 변수 배치 순서 및 시작 도시와 도착 도시 사이의 연결이 없는 경우를 0으로 표시하는 부분에 유의하여 프로그래밍 하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int D[100][100];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, M;
	cin >> N >> M;

	while (M--)
	{
		int from, dest, cost;
		cin >> from >> dest >> cost;

		if (D[from - 1][dest - 1])
			D[from - 1][dest - 1] = cost < D[from - 1][dest - 1] ? cost : D[from - 1][dest - 1];
		else
			D[from - 1][dest - 1] = cost;
	}

	for (int w = 0; w < N; w++)
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
			{
				if (i == j || w == i || w == j)
					continue;

				if (D[i][w] && D[w][j])
					if (!D[i][j] || 
						D[i][j] > D[i][w] + D[w][j])
						D[i][j] = D[i][w] + D[w][j];
			}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			cout << D[i][j] << " ";
		cout << "\n";
	}

	return 0;
}

 

실행 결과