백준 11403: 경로 찾기

문제 요약

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

문제 분류

• 그래프 이론
• 그래프 탐색
• 최단 경로
• 플로이드-워셜

문제 풀이

ary배열에서 ary[j][i]와 ary[i][k]가 모두 연결되어 있을 경우, ary[j][k]도 연결되어있다는 것이 핵심이다.

즉, i를 먼저 잡고, j와 k를 이중 for문의 변수로 선언하여 순회하면 된다. 이 for문이 끝남과 동시에 i도 n까지 순회시킨다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	int ary[100][100] = { 0, };
	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &ary[i][j]);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++)
				if (ary[j][i] + ary[i][k] > 1) ary[j][k] = 1;

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

	return 0;
}