[C++] BOJ 11403 경로 찾기

문제

백준 11403번 https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

코드

#include<iostream>
using namespace std;

int n, arr[101][101];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> ans[i][j];
		}
	}
	//k 경유
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (ans[i][k] && ans[k][j]) ans[i][j] = 1;
			}
		}
	}
    //출력
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << ans[i][j] << ' ';
		}
		cout << '\n';
	}
}

풀이방법

방향 그래프를 배열에 입력받고, 플로이드-와샬 알고리즘을 이용해서 특정 경유점에 대해 경로가 존재하면 배열의 값을 바꿔줬다.

고민과정

최소경로값을 안써서 그런지 브루트포스의 느낌이 강했다.