[백준-9466] 텀 프로젝트

이 문제는 백준 골드 4 레벨의 텀 프로젝트 라는 문제이다. 

 

이 문제는 그래프에서 싸이클을 찾는 문제이다.

싸이클이 발생하는 경우에만 한 팀으로 인정한다.

그래서 dfs를 사용했다.

 

입력은 똑같이 받아주면 되고,

dfs를 돌 때, 모든 노드들이 연결되어 있는것이 아니기 때문에 한번만 돌면 방문하지 않는 학생이 생길수도 있다.

따라서 학생 수 만큼 돌려줄 것이다.

 

1) 학생 수 만큼 for문을 돌면서 

2) 방문 한 학생이라면 pass

3) i번 학생이 선택한 곳을 들어가지 않았다면 들어가보기.

  3-1) 계속해서 dfs를 돌다가, 다음곳을 이미 방문했고, 시작점과 만났다면 level - check[next]+1 값을,

  3-2) 시작점이 아닌 다른 곳이 나왔다면 0을 return 해준다. 

 

import java.util.LinkedList;
import java.util.Scanner;

public class 텀프로젝트_9466 {
	static int T;
	static int N;
	static int[] student;
	static int[] check; //방문여부
	static int[] cycle; //사이클인지 아닌지 

	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for(int tc=0; tc<T; tc++) {
			N = sc.nextInt();

			student = new int[N+1];
			check = new int[N+1];
			cycle = new int[N+1];
			int cnt=0;
			
			for(int i=1; i<=N; i++) { //각 학생이 원하는 학생 입력
				student[i] = sc.nextInt();
			}
			
			for(int i=1; i<=N; i++) {
				if(check[i] !=0) //방문 했으면 넘기기
					continue;
				if(check[student[i]] == 0) {//i번 학생이 선택한 곳 안갔으면
					cnt+= dfs(i,i,1); //cnt에 값 더해줌
				}	
			}
			System.out.println(N-cnt);
		}
	}
	
	static int dfs(int start, int num, int level) {
		check[num] = level;
		cycle[num] = start;
		
		int next = student[num];
		if(check[next]!=0 && start == cycle[next])
			return level - check[next]+1;
		else if(check[next]!=0 && start != cycle[next])
			return 0;
		
		return dfs(start, next, level+1);
	}

}