[BOJ] 9466번_텀 프로젝트_DFS (C++)

[문제]

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

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 한 명만 선택할 수 있다.) 혼자하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들을 S1, S2, ..., Sr 이라 할 때, r=1이고 S1이 S1을 선택하는 경우나, S1이 S2를 선택하고, S2가 S3를 선택하고, ..., Sr-1이 Sr을 선택하고, Sr이 S1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

위의 결과를 통해 (3)과 (4,7,6)이 팀을 이룰 수 있다. 1,2,5는 어느 팀에도 속하지 않는다. 주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하는 문제이다.

[사용 알고리즘]

DFS(깊이 우선 탐색)

[풀이 핵심]

• DFS를 돌다가 이미 방문한 노드를 만나면 사이클을 이룬다는 것이기 때문에 사이클을 이룬 학생들의 수를 전체 학생 수에서 빼주면 된다. 그리고 다음 DFS에서부턴 방문하지 않도록 group배열에 기록해준다.
• 아래와 같은 for문으로 사이클을 이루는 학생 수를 전체 학생 수에서 빼주면서 답을 구해준다. (백 트래킹)

for (int i = graph[V]; i != V; i = graph[i]) {
	result--;
}

[코드]

//boj9466_텀 프로젝트_그래프

#include<iostream>
#include<set>

using namespace std;

int graph[100001];
bool visited[100001];
bool group[100001];

int result;

void DFS(int V) {
	visited[V] = true;

	if (!visited[graph[V]]) {
		DFS(graph[V]);
	}
	else {
		if (!group[graph[V]]) {
			for (int i = graph[V]; i != V; i = graph[i]) {
				result--;
			}
			result--;
		}
	}
	group[V] = true;
}

int main() {
	int T;
	cin >> T;
	for (int t = 0; t < T; t++) {
		for (int i = 0; i < 100001; i++) {
			visited[i] = false;
		}
		for (int i = 0; i < 100001; i++) {
			group[i] = false;
		}

		int N;
		cin >> N;

		result = N;

		for (int i = 1; i <= N; i++) {
			cin >> graph[i];
		}

		for (int i = 1; i <= N; i++) {
			if (!visited[i]) {
				DFS(i);
			}
		}
		cout << result << '\n';
	}
	return 0;
}