[dfs] 백준 11403 경로 찾기

하용권 2019. 3. 27. 21:24

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

11403번: 경로 찾기

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

www.acmicpc.net

#include <iostream>
#include <vector>
using namespace std;
vector<int> v[100];
int ret[100][100] = {0};
int n;

void dfs(int start, int y){
	
	for(int i = 0; i < v[start].size(); i++){
		int tmp = v[start][i];
		if(ret[y][tmp]) continue;
		ret[y][tmp] = 1;
		dfs(tmp,y);
	}
}

int main(){
	int tmp;
	cin >> n;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> tmp;
			if(tmp == 1)
				v[i].push_back(j);
		}	
	}
	
	
	for(int i = 0; i < n; i++){
		dfs(i,i);
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++)
			cout << ret[i][j] << ' ';
		cout << endl;
	}
}