[BOJ/C++] 11403 경로 찾기 : DFS

문제

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

풀이

문제를 잘 읽자👀
가중치 없는 '방향' 그래프인데 내 멋대로 방향 없는 그래프라고 봄;

자기 자신으로 갈 수 있냐 없냐도 고려해야하기 때문에 visited 표시하는 위치를 바꿔야 함

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> v[101];
bool check[101];
int ans[100][100];
int N;

void dfs(int node) {
	for (int i = 0; i < v[node].size(); i++) {
		int next = v[node][i];

		if (!check[next]) {
			check[next] = true;
			dfs(next);
		}
	}
}

void check_ans(int node) {
	for (int i = 0; i < N; i++) {
		ans[node - 1][i] = check[i + 1];
	}
}

int main() {
	int a[100][100] = { 0, };
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int tmp;
			cin >> tmp;
			a[i][j] = tmp;
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (a[i][j] == 1) {
				v[i+1].push_back(j+1);
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		dfs(i);
		check_ans(i);
		fill_n(check, 101, false);
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << ans[i][j] << ' ';
		}
		cout << '\n';
	}

	return 0;
}