🩶I [백준 11403/C++] 경로 찾기

BOJ 링크

---

문제

풀이

플로이드-워셜의 기초 문제다.

graph[i][k]와 graph[k][j]의 간선이 존재하면, graph[i][j]의 간선 역시 존재한다. => 플로이드-워셜의 기본 알고리즘!

모든 노드를 출발점으로 삼고, 모든 노드를 도착 노드로 최단 거리를 구하므로, 3중 반복문을 사용한다.

cf) 다익스트라/벨만포드 알고리즘은 한 노드에서 모든 노드까지의 최단 경로를 구한다.

시간 복잡도는 $O(n^{3})$이다. 그래프가 충분히 작을 경우 사용하자!

코드

#include <iostream>

int graph[101][101];

int main()
{
	// init & input
	int n;
	std::cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			std::cin >> graph[i][j];
		}
	}

	// floyd-warshall
	for (int k = 0; k < n; k++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (graph[i][k] && graph[k][j]) graph[i][j] = 1;
			}
		}
	}

	// output
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			std::cout << graph[i][j] << " ";
		}
		std::cout << "\n";
	}

	return 0;
}