[BOJ/C++] 11403(경로 찾기)

Link: https://www.acmicpc.net/problem/11403

• Floyd-Warshall 알고리즘을 알고 있다면 바로 풀 수 있던 문제라고 생각

모든 정점(i,j)에 대해 i에서 j로 가는 길이가 양수인 경로 여부 -> Floyd-Warshall

#include<iostream>
using namespace std;

int n;
int dist[100][100];

void input() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> dist[i][j];
		}
	}
}


void solution() {
	input();
	for (int m = 0; m < n; ++m) {
		for (int s = 0; s < n; ++s) {
			for (int e = 0; e < n; ++e) {
				if (dist[s][m] == 1 &&  dist[m][e] == 1) {
					dist[s][e] = 1;
				}
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cout << dist[i][j] << ' ';
		}cout << '\n';
	}
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	solution();
	return 0;
}