BOJ (C/C++) 11403번: 경로 찾기

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

11403번: 경로 찾기

---

풀이

모든 정점의 경로를 구해야 하므로 플로이드-워셜 알고리즘을 사용했다.또한 방향 그래프이므로 출발-중간-도착으로의 경로가 모두 존재해야 경로가 있다고 판단한다.

---

코드

#include <stdio.h>
int main() {
	int N, A[100][100];

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			scanf("%d", &A[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 (A[i][k] == 1 && A[k][j] == 1) A[i][j] = 1;
			}
		}
	}

	// Print
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			printf("%d ", A[i][j]);
		}
		printf("\n");
	}

	return 0;
}