[백준]Baekjoon9466(DFS,cycle)

문제링크 : https://www.acmicpc.net/problem/9466

생각보다 푸는데 어려움을 느꼈던 문제이다.

원래 DFS를 푸는 방식을 조금 변형할 필요가 있다. 

예를들어 1 -> 3 , 3 -> 5, 5 -> 3 이라고 가정할 때 기존의 방법대로 탐색을 하면

1 -> 3 -> 5 에서 5의 다음 노드가 3이고 3은 이미 지나간 노드이기 때문에 이제 처리를 해야한다.

여기서 이 문제만의 독특한 점은 이 탐색 안에서 따로 cycle을 찾아야한다는 것이다.

그러니까 위의 예시로 치면 3 -> 5 -> 3을 발견해야하며 숫자가 많아질 수록 복잡해질 것이다.

cycle을 어떻게 찾을까에 대해 생각해보면

명확한 점은 한번씩 탐색을 한 다음 이미 지나간 노드라고 처음 인식한 지점이 실제 cycle의

첫번째 지점이라는 것이다.

그래서 이 노드부터 다시 이 노드가 나올 때까지의 숫자를 계산한다면 cycle을 이루는 갯수를

알 수 있다.

#include <iostream>

using namespace std;

int arr[100001];
bool check[100001];
bool finished[100001]; //이미 발견한 cycle로 다시 들어가는 것을 막기위한 장치
// 예를들어 1 -> 3 -> 5 -> 1 이라는 cycle을 발견하고 처리한 후 
// 7 -> 3 이라는 탐색을 했을 때 문제가 될 수 있다.
int cnt; //cycle의 갯수

void DFS(int start)
{
	check[start] = true; //지나간 것 표시
	int next = arr[start]; //다음 노드
	if (!check[next]) DFS(next); //다음 노드를 아직 지나가지 않았다면 ㄱㄱ
	else {//다음 노드가 지나간 노드라면
		if (!finished[next]) { //그 다음 노드가 이미 cycle로 발견한 것이 아닐 때
			for (int x = next; x != start; x = arr[x]) {
				cnt++; //다음 노드를 시작점으로 해서 다시 돌아올 떄까지
			}          //갯수를 더한다.
			cnt++;
		}
	}
	finished[start] = true; //위와같은 과정이 완료된 노드에 대해 표시를 해줌
}

int main()
{
	int testcase,n;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &arr[i]);
			check[i] = false;
			finished[i] = false;
		} //초기화
		int result = 0; //조를 이룰 수 있는 사람 수
		for (int i = 1; i <= n; i++) {
			cnt = 0;
			if (!check[i]) {
				DFS(i);
				result += cnt;
			}
		}
		printf("%d\n", n - result);
	}
		
}