[백준 11403] 경로 찾기

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

11403번: 경로 찾기

요구사항

1. 노드에서 노드로 이동가능한지 여부 확인하기

 

풀이

그래프로 입력이 주어진다.

모든 그래프를 탐색하여 이동 경로가 존재할 경우, 노드에서 이동 가능한 모든 노드를 탐색한다.

 

#include <iostream>
#include <string.h>

using namespace std;
int n;
int map[102][102];
int ans[102][102];
int visit[102];
void dfs(int start, int next) {
	
	for (int i = 1; i <= n; i++) {
		if (map[next][i] == 1) {
			if (visit[i] == 0) {
				visit[i] = 1;
				ans[start][i] = 1;
				dfs(start, i);
			}
		}
	}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++)
		{
			if (map[i][j] == 1) {
				memset(visit, 0, sizeof(visit));
				ans[i][j] = 1;
				dfs(i, j);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			printf("%d ", ans[i][j]);
		}
		printf("\n");
	}
}