[백준] 9466번 텀 프로젝트 (C++)

9466번: 텀 프로젝트

DFS로 풀 수 있는 문제이다.

팀이 구성되는 경우는 사이클이 생기는 경우라 생각하면 된다.

 

사이클이 생기는 경우를 찾아주기 위해 current와 visited 배열이 필요하다.

current엔 stack에 들어가 있는 애들을 표시해주고

visited는 비교가 끝난 애들을 체크해준다.

 

사이클이 생기는 경우엔 사이클의 시작과 끝을 담당하는 애를 leader에 넣어주고

current를 참고하여 사이클이 형성되는 부분까지는 팀이 구성되는 걸로 간주하여 카운트 값을 하나씩 줄여준다.

visited에도 표시를 해주어 더 이상 비교 대상에 들어가지 않게 한다.

 

사이클은 끝났는데 stack에 남아 있는 애들은 팀이 구성될 수 없기 때문에

전부 pop해주고 역시 visited도 표시해준다.

 

여기서 stack에 값을 push하기 전에 push할 값(top이 가리키고 있는 애)이 이미 visited된 상태라면

stack에 있는 애들은 팀을 구성할 수 없는 애들이므로

전부 pop해주고 visited에도 표시해준다.

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

int cnt;
void Dfs(int idx, int N, int student[], int visited[], int current[]) {
	stack <int> st;
	st.push(idx);
	current[idx] = 1;
	while (1) {
		if (visited[student[st.top()]]) {
			while (!st.empty()) {
				current[st.top()] = 0;
				visited[st.top()] = 1;
				st.pop();
			}
			break;
		}
		st.push(student[st.top()]);
		if (current[st.top()]) { //사이클이면
			int leader = st.top();
			if (visited[leader] == 0) {
				visited[leader] = 1;
				cnt--;
			}
			current[leader] = 0;
			st.pop();
			while (leader != st.top()) { //사이클이 형성되는 곳까진 팀이 구성 됨
				cnt--;
				visited[st.top()] = 1;
				current[st.top()] = 0;
				st.pop();
			}
			st.pop();
			while (!st.empty()) { //그 외는 팀이 될 수 없음
				visited[st.top()] = 1;
				current[st.top()] = 0;
				st.pop();
			}
			break;
		}
		else current[st.top()] = 1;
	}
}

int main() {
	int T, N;
	cin >> T;
	for (int t = 0; t < T; t++) {
		int student[100001] = { 0 }, visited[100001] = { 0 }, current[100001] = { 0 };
		cin >> N;
		for (int n = 1; n <= N; n++) cin >> student[n];
		cnt = N;
		for (int i = 1; i <= N; i++) {
			if (visited[i] == 0) Dfs(i, N, student, visited, current);
		}
		cout << cnt << "\n";
	}

	return 0;
}

원리는 이 영상을 참고했다.

여기서 설명하는 white set은 student 배열,

gray set은 current 배열,

black set은 visted 배열이다.