[백준] 알고리즘 9466번 - 텀 프로젝트 문제

#include <bits/stdc++.h>
using namespace std;
int arr[100001]; // 학생 정보 저장
int check[100001]; // 방문했나 안했나
int first_student[100001]; // 첫번째 방문 요소 저장

int dfs(int first,int now,int cnt) {
    if (check[now]) {
        if (first_student[now] != first)
            return 0;
         return cnt - check[now];
    }
    first_student[now] = first;
    check[now] = cnt;
    return dfs(first,arr[now],cnt+1);
}
int main(){
    int T;
    cin >> T;
    while (T--) {
        int n,ans=0;
        cin >> n;
        for (int i = 1; i <= n; i++) 
            cin >> arr[i];
        for (int i = 1; i <= n; i++) {
            if(!check[i]){
                ans += dfs(i, i, 1);
            }
        } 
        cout << n-ans << "\n";
        for (int i = 1; i <= n; i++) {
            arr[i] = 0;
            check[i] = 0;
            first_student[i] = 0;
        }
    }
}

사이클이 되었을 경우, 어디서 부터 사이클인지 판별하기 위한 방문횟수가 필요함.
1.  처음 시작점을 지정해줘야 한다.
2.  방문횟수가 0이 아닌경우 즉, 사이클이 형성되는 경우이다. 이 경우에 만약 처음 시작점과 사이클이 끝나는 지점이 같을 경우 하나의 사이클이 완성된 경우고, 다를 경우 완전한 사이클을 이루지 못한 경우로써 (여태 방문한 횟수 - 이전에 방문했던 값을 빼면된다.)

이 문제의 경우 정말 처음 접하는 느낌의 dfs여서 상당히 어렵게 느껴졌다.

다른분들의 해설을 참고하여 이해하였지만, 이해하는데 시간이 엄청 걸렸습니다.

이렇게 이해가 안되는 문제는 다른 분들의 해설을 보고 이해하는 것도 중요하드는 것을 깨달았습니다.