[백준] 텀 프로젝트 (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까지 번호가 부여된다.)

출력

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

---

까다로운 dfs 문제였다.

사이클에 포함되지 못하는 노드의 수를 구하는 게 관건이었다.

1 - 2 - 3 - 1 - 2 - 3... 같은 평범한 사이클을 구하는 건 문제가 안되지만, 1 - 2 - 3 - 3 - 3 .. 같은 중간에 사이클이 생기는 경우가 문제였다. 

해결 방법은 visit 배열과 함께 처음 방문을 시작하게 된 지점을 저장하는 first 배열을 활용하는 것이다.

1 - 2 - 3 - 3 - 3 같은 경우 first 배열값은 모두 시작점인 1이 저장된다.

그래서 방문을 했고 동시에 시작점이 같은 경우 cycle의 개수를 반환하면 되는 것이다. 코드를 보고 이해하자.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%ED%85%80%20%ED%94%84%EB%A1%9C%EC%A0%9D%ED%8A%B8%20(9466%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <cstring>
using namespace std;
int T, N;
int p[100001];
int first[100001];
int visit[100001];

int dfs(int start, int x, int cnt)
{
	visit[x] = cnt; //방문회수
	first[x] = start; //시작점 기록
	int nx = p[x];
	if (visit[nx] == 0) return dfs(start, nx, cnt + 1); //방문안했으면 방문
	else if (first[nx] == start) return cnt - visit[nx] + 1; //방문한점이면 cycle의 수 반환.
	else return 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> T;
	while (T--) {
		cin >> N;
		memset(p, 0, sizeof(p));
		memset(first, 0, sizeof(first));
		memset(visit, 0, sizeof(visit));
		for (int i = 1; i <= N; i++) cin >> p[i];

		int res = 0;
		for (int i = 1; i <= N; i++) {
			if (visit[i] == 0) {
				res += dfs(i, i, 1);
			}
		}
		cout << N - res << "\n";
	}
}