[백준 C++] 9466 텀 프로젝트 - 깊이우선탐색

9466번: 텀 프로젝트

#include <iostream>
#include <cstring>
using namespace std;

int N, Cnt;
int Student[100000];
bool Visited[100000];
bool Check[100000];

void DFS(int Current)
{
	Visited[Current] = true;

	int Next = Student[Current];
	if (!Visited[Next])
	{
		DFS(Next);
	}
	else if (!Check[Next])
	{
		for (int i = Next; i != Current; i = Student[i])
		{
			++Cnt;
		}

		++Cnt;
	}

	Check[Current] = true;
}

void Test()
{
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		int Num;
		cin >> Num;
		Student[i] = Num - 1;
	}
	
	memset(Visited, false, sizeof(Visited));
	memset(Check, false, sizeof(Check));

	Cnt = 0;
	for (int i = 0; i < N; ++i)
	{
		if (!Check[i])
		{
			DFS(i);
		}
	}

	cout << N - Cnt << '\n';
}

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

	int T;
	cin >> T;
	for (int i = 0; i < T; ++i)
	{
		Test();
	}
}

---

 

방문 체크 배열과 팀 결과 확인 체크 배열 두 개를 관리해서 시간복잡도를 최소화하는 DFS 문제입니다.

팀 결과를 확인하지 않은 각 노드에 DFS를 이용해서 해당 노드가 팀이 있는지 없는지 체크하도록 합니다.

 

DFS에서 싸이클이 이루어지는 경우 (다음 노드가 이미 방문한 노드면서 팀 결과 확인을 아직 하지 않았을 때)

현재 노드를 제외한 팀원들의 개수만큼 카운팅해줍니다.

그다음 현재 노드까지 카운팅 +1 해줍니다. (팀원이 한 명일 경우에는 이 두 절차를 통해 팀원 개수 카운팅이 총 1이 됨)

 

팀에 속한 노드 수를 세고나면 빠져나오면서 방문했던 노드들은 모두 팀 결과를 확인했다는 표시를 해줍니다.