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

 

문제

---

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

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

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

1	2	3	4	5	6	7
3	1	3	7	3	4	6

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

 

9466번: 텀 프로젝트

 

문제조건

---

2 ≤ n ≤ 100,000

 

풀이

---

시간 초과로 애를 먹은 문제이다. 이 문제의 경우 모든 탐색은 사이클이 있어야 끝나기 때문에 bfs의 종료조건을 방문했던 곳을 다시 방문하는 경우로 풀어주었다. 하지만 그냥 dfs로 하다보면 이미 사이클임을 확인한 곳을 다시 방문하게 되어 O(\(n^2\))으로 시간 초과가 일어난다. 오랫동안 생각해봐도 방법을 모르겠어서 답을 찾아보았다.

첫번째 방법

 

https://jaimemin.tistory.com/674

백준 9466번 텀 프로젝트

내가 시도한 방법에서 done이라는 배열을 추가하여 이미 사이클을 만든 학생들은 다시 방문하지 않게 하여 시간을 줄이는 방법이다. 배열을 추가할 생각은 못했었는데 간단하게 해결이 되서 놀라웠다. from==to를 확인하기 위해 while문을 썼었는데 for문으로도 확인할 수 있다는 것을 알 수 있었다.

 

두번째 방법

 

https://lmcoa15.tistory.com/51

백준 9486번 - 텀 프로젝트

전혀 생각하지 못한 방법이다. 사이클을 이룰 시 마지막 cnt에서 다시 방문하는 cnt를 빼주어 cycle의 개수를 세어줄 수 있다는 것을 배울 수 있었다.

 

코드

---

#include<iostream>
#include <cstring>
using namespace std;
int n;
int student[100001];
bool visited[100001];
bool done[100001];
int cnt;

void check(int from) {
	visited[from] = true;
	int to = student[from];
	if (!visited[to]) {
		check(to);
	}
	else if (!done[to]){
		//내부에 사이클이 있음
		for (int i = to; i != from; i = student[i]) {
			cnt++;
		}
		cnt++;
	}

	done[from] = true; // 다시 방문x
}

int main() {
	int t;
	cin >> t;

	for (int j = 0; j < t; j++) {
		cin >> n;
		cnt = 0;
		memset(visited, false, sizeof(visited));
		memset(done, false, sizeof(done));

		for (int i = 1; i <= n; i++) {
			int s;
			cin >> s;
			student[i] = s;
		}

		for (int i = 1; i <= n; i++) {
			if(!visited[i]) check(i);
		}
		
		cout << n-cnt << "\n";
	}
}