[C++] 백준 9466 : 텀 프로젝트

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

9466번: 텀 프로젝트

백준 9466번 텀 프로젝트를 풀었다.

 

처음엔 단순하게 모든 학생들을 순회하면서 DFS를 실행하고 싸이클이 존재할 때 카운트를 세는 방식을 사용했는데 시간 초과가 나왔다.

고민을 하다가 구글에 검색해서 문제 풀이를 찾아봤는데 visited 배열 말고도 done 배열을 같이 사용하는 것을 확인했다.

https://wooono.tistory.com/409

위의 블로그를 참고해서 문제를 풀었다.

 

배열의 설명부터 해보면

choice 배열 : 함께하고 싶은 학생의 index를 저장

 

visited 배열 :

- 0일 때 : 아직 방문하지 않은 학생

- 1일 때 : 방문한 학생

 

done 배열:

- 0일 때 : 아직 팀 매칭 결과를 모르는 학생

- 1일 때 : 팀 매칭 결과를 아는 학생

 

반복문을 통해 DFS를 실행할 때, 입력 받은 학생을 방문처리 한다.

그 다음 next에 입력 받은 학생이 원하는 학생의 index를 저장한다.

visited[next]를 확인해서 방문한 적이 없다면 DFS(next)를 실행한다.

visited[next]를 확인해서 방문한 적이 있지만, done[next]를 확인해서 팀 매칭이 끝나지 않은 학생이라면 싸이클이 존재한다는 뜻이므로 현재 싸이클을 이루는 학생들의 수를 센다.

 

전체 학생 수에서 팀이 된 학생의 수를 빼서 결과를 출력한다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <algorithm>
#pragma warning(disable:4996)

using namespace std;

int t, n;
int cnt;
int choice[100001];
int visited[100001];
int done[100001];

void DFS(int k) {
	visited[k] = 1;
	int next = choice[k];
	if (visited[next] == 0) {
		DFS(next);
	}
	else if (done[next] == 0) {
		for (int i = next; i != k; i = choice[i]) {
			cnt++;
		}
		cnt++;
	}
	done[k] = 1;
}

int main() {
	cin >> t;
	while (t--) {
		cin >> n;

		for (int i = 1; i <= n; i++) {
			scanf("%d", &choice[i]);
		}

		cnt = 0;
		for (int i = 1; i <= n; i++) {
			DFS(i);
		}

		for (int i = 1; i <= n; i++) {
			choice[i] = 0;
			visited[i] = 0;
			done[i] = 0;
		}

		cout << n - cnt << "\n";
	}

	return 0;
}