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

문제 링크이다.

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

9466번: 텀 프로젝트

 

사이클을 탐색할 수 있으면 해결할 수 있는 문제이다.

 

팀이 결정되는 조건이 결국 사이클을 이루는 조건이기 때문이다.

 

 

사이클을 검사할 때 템플릿처럼 활용할 수 있을 것 같다.

 

먼저 방문처리 배열을 두 개를 둔다.

 

vis배열은 0인 경우 아예 방문을 하지 않은 것이고, -1인 경우에는 방문을 했고, 더 이상 방문할 필요가 없다는 것이다.

 

1인 경우에는 현재 방문 중이라는 의미이다.

 

Done배열은 사이클을 이루는 성분인지 여부를 저장한다.

 

만약 학생 x를 한번 방문해서 vis[x]가 1인 상태라고 해보자. 즉 방문하고 있는 중이라는 것인데,

 

이 상태에서 x를 누군가가 또 방문한다는 것은? 학생 1을 포함하는 사이클이 존재한다는 의미이다.

 

따라서 x는 사이클이라는 것이 확실하기 때문에 done[x]를 true로 설정해준다.

 

그리고 cycle 검사를 마치면 (재귀를 탈출하면) 더 이상 방문할 필요가 없다는 의미이기 때문에 vis[x]를 -1로 만들어준다.

 

결과적으로 cycle검사의 탈출 조건은 이미 방문할 필요가 없는 곳이거나(vis가 -1인 경우)

 

이미 사이클을 이루고 있는 경우(Done이 1인 경우)인 것이다.

 

	/*
	방문한적 없으면 방문
	방문처리
	다음방문(방문이 끝나면 방문 확정처리)
	이미 방문한 적이 있는 지점 -> 사이클
	방문 확정처리 된 지점 or 사이클로 판정된 지점 -> 더 이상 진행할 필요가 없음
	*/
	#include<iostream>
	using namespace std;
	int stu[100001], vis[100001];
	bool Done[100001];
	int n, cnt = 0;
	void cycle(int k) {
	if (Done[k] == true || vis[k] == -1)
	return;
	if (vis[k] == 0)
	vis[k] = 1;
	else if (vis[k] == 1) {
	Done[k] = true;
	cnt++;
	}
	cycle(stu[k]);
	vis[k] = -1;
	}
	int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
	cin >> n;
	for (int i = 1; i <= n; i++)
	cin >> stu[i];
	for (int i = 1; i <= n; i++) {
	if (vis[i] == 0)
	cycle(i);
	}
	cout << n -cnt << '\n';
	for (int i = 1; i <= n; i++) {
	stu[i] = 0;
	vis[i] = 0;
	Done[i] = false;
	}
	cnt = 0;
	}
	return 0;
	}

view raw boj_9466_텀프로젝트.cpp hosted with ❤ by GitHub