플로이드-워셜을 이용한 문제이다. 반복문을 돌면서 A[i][k]
와 A[k][j]
의 간선이 존재한다면 A[i][j]
에 1을 저장해주고 출력해주었다.
플로이드-워셜 알고리즘을 풀어본 적이 있어서 간단하게 풀 수 있었다.
#include <iostream>
using namespace std;
int N;
int A[100][100];
void solution() {
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (A[i][k] && A[k][j]) {
A[i][j] = 1;
}
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << A[i][j] << " ";
}
cout << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> A[i][j];
}
}
solution();
return 0;
}