[BOJ] 백준 9466 텀 프로젝트 c++ (dfs)

문제 출처 : https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

---

풀이

프로젝트 팀에 속하지 못한 학생의 수를 구하는 문제이다.

 

방문 완료 처리(done) - dfs 

기존 dfs에서 check(방문)배열은 많이 사용했었지만, 이 문제는 방문 완료(done) 처리가 필요하다.

 

한 프로젝트에 참여하는 모든 팀원을 구하기 위해, check 되지 않았다면 dfs를 재귀호출한다.

그 후 for문을 통해 팀원의 카운트를 구한 후, 방문 완료 처리를 한다.

void dfs(int now) {
	check[now] = true;
	int next = v[now];

	if(!check[next])
		dfs(next);
	else if(!done[next]) {
		for(int i = next; i != now; i = v[i]) {
			cnt++;
		}
		cnt++; // 본인
	}
	done[now] = true;
	return;
}

---

코드

#include <bits/stdc++.h>

using namespace std;

vector<int> v;
bool check[100001];
bool done[100001];
int cnt; // 프로젝트 팀 결성

void dfs(int now) {
	check[now] = true;
	int next = v[now];

	if(!check[next])
		dfs(next);
	else if(!done[next]) {
		for(int i = next; i != now; i = v[i]) {
			cnt++;
		}
		cnt++; // 본인
	}
	done[now] = true;
	return;
}

int main(void) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);	

	int T; cin >> T;
	while(T--) {
		int n; cin >> n;
		v.resize(n+1);
		for(int i = 1; i <= n; i++) {
			cin >> v[i];
		}

		for(int i = 1; i <= n; i++) {
			if(!check[i])
				dfs(i);
		}
		cout << n - cnt << '\n';
		cnt = 0;
		memset(check, false, sizeof(check));
		memset(done, false, sizeof(done));
	}
	return 0;
}