문제 링크

---

설명

플로이드 와샬 : 모든 정점에서 모든 정점으로의 최단경로

초기 인접행렬 상태에서 k를 거쳐서 i, j를 가는 경로가 있으면 [i][j] = 1해주면서 계속 갱신해주는 방식

• 2->0, 0->1인 경로 존재, (2,1)
• 0->1, 1->2인 경로 존재, (0,2)
• 2->1, 1->2인 경로 존재, (2,2)
• 0->2, 2->0인 경로 존재, (0,0)
• 0->2, 2->1인 경로 존재, (0,1)
• 0->2, 2->2인 경로 존재, (0,2)

---

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int arr[100][100];
int n;

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

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> arr[i][j];

	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (arr[i][k] && arr[k][j])
					arr[i][j] = 1;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cout << arr[i][j] << ' ';
		cout << endl;
	}

	return 0;
}