[BJ] 9466 : 텀 프로젝트

       문제 요약        

- 문제

 

 

- 입출력

 

         아이디어        

- 사이클 찾는 문제 + 방향 그래프 

         소스코드        

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution {
	static int TESTCASE;
	static int[] student;
	static boolean[] checkCycle;
	static boolean[] visited;
	static int ans;
	public static void main(String[] args)throws Exception{
		BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
		TESTCASE = Integer.parseInt(br.readLine());
		for(int tc = 1; tc <= TESTCASE; tc++) {
			int studentCnt = Integer.parseInt(br.readLine());
			student = new int[studentCnt+1];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int i = 1; i <= studentCnt; i++) {
				student[i] = Integer.parseInt(st.nextToken());
			}
			
			checkCycle = new boolean[studentCnt + 1];
			visited = new boolean[studentCnt + 1];
			// 시작하는 곳으로 되돌아올 수 있어야 함 
			for(int i = 1; i <= studentCnt; i++) {
				if(!checkCycle[i]) {
					dfs(i);
				}
			}
			System.out.println(ans);
		
		}
	}	
	static void dfs(int cur) {
		if(visited[cur]) { // 방문했는데 또 방문한 경우, cycle 구성원
			checkCycle[cur] = true;
			ans += 1;
		}
		visited[cur] = true;
		
		
		int next = student[cur];
		if(!checkCycle[next]) {
			dfs(next);
		}
		
		visited[cur] = false; // 방문 처리 종료
		checkCycle[cur] = true; // 사이클에 들어가지 않았다면 더 이상 사이클 처리를 해도 의미가 없음
		
	}

}