[백준] 9466번 - 텀 프로젝트 - C/C++

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

9466번: 텀 프로젝트

 

문제

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

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

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

1234567

3

1

3

7

3

4

6

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

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

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

---

 

    그래프에서 사이클이 있는지 확인하는 문제이다. 사이클의 존재 여부를 확인하려면 방문 여부를 확인하는 배열( vis[] )과 dfs가 종료되었는지 확인하는 배열( finished[] ) 두 개가 필요하다. dfs를 활용하면서 그래프를 순회한다. 한 노드에 들어가서 다음 노드를 방문하지 않았다면 방문한다. 방문하였는데 해당 노드의 dfs가 종료되지 않았다면 (finished == false) 순회 중 사이클이 발견된 경우이다. 그 경우 해당 사이클을 순회하며 개수를 저장해둔다. 이 모든 작업이 끝났다면 해당 노드에서 순회가 종료된 것이므로 finished[node] = true로 세팅해준다. 

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

int n,ans=0;
int arr[100001];
bool vis[100001];
bool finished[100001];

void dfs(int node) {
	vis[node] = true;
	int next = arr[node];

	if (!vis[next]) {
		dfs(next);
	}
	else if (!finished[next]) {
		for (int i = next; i != node; i = arr[i]) {
			ans++;
		}
		ans++;
	}
	finished[node] = true;
	return;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int tc;

	cin >> tc;

	while(tc--) {
		ans = 0;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
			vis[i] = false;
			finished[i] = false;
		}
		for (int i = 1; i <= n; i++) {
			if (!vis[i]) dfs(i);
		}

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


	return 0;
}

---

    dfs 로 쉽게 풀 수 있는 문제인 것 같았는데 예상외로 사이클을 구하는 부분에서 애를 먹었다. 처음에는 인접한 노드가 하나뿐이기 때문에 recursion이나 iterative 나 비슷해 보여 iterative 하게 구해보려고 했지만 시간 초과가 났다. 그때에도 배열 두 개를 활용하면서 하기는 했는데 memset을 많이 해야 하는 구조여서 시간 초과가 났다. 그래서 싹 다 지우고 dfs로 처음부터 다시 짰다. 그럼에도 쉽지 않았는데 생각해보니 사이클을 구해본 적이 없는 것 같았다. 이제는 사이클 구하는 코드를 해보았으니 다음부터는 안 헤매야겠다!