[백준] 9466 : 팀 프로젝트 JAVA 풀이

 

뭔가 풀릴 듯 안 풀려서 결국 구글링의 힘을 빌렸다.

 

학생들이 선택한 학생번호를 저장할 int 배열,

각 학생들의 팀 배정이 완료됐는지 확인하는 boolean 배열,

한 바퀴를 돌았는지(=두 번째 방문한 건지) 확인하는 boolean 배열이 필요하다.

 

 

import java.io.*;
import java.util.*;

public class Main{
    static boolean[] visit, done;
    static int[] arr;
    // 완성된 팀의 개수
    static int cnt;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 테스트케이스의 개수를 입력받음
        int T = Integer.parseInt(br.readLine());
        
        for(int i=0;i<T;i++){
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            
            arr = new int[n+1];
            visit = new boolean[n+1];
            done = new boolean[n+1];
            cnt = 0;
            
            for(int j=1;j<=n;j++){
                arr[j] = Integer.parseInt(st.nextToken());
            }
            
            // 아직 팀이 정해지지 않은 학생에 대해 dfs 수행
            for(int j=1;j<=n;j++){
                if(!done[j]){
                    dfs(j);
                }
            }
            System.out.println(n-cnt);
        }
        
    }
    
    public static void dfs(int v){
    	// 이미 방문했던 곳이라면 == 한 바퀴 돈 거라면
        if(visit[v]){
        	// 팀 배정 완료로 체크 후 cnt++
            done[v] = true;
            cnt++;
        }
        else{
        	// 처음 방문한 거라면 방문했다고 체크
            visit[v] = true;
        }
        
        // 자신이 선택한 학생이 아직 팀 배정이 안됐다면
        // dfs 수행
        if(!done[arr[v]]){
            dfs(arr[v]);
        }
        
        // dfs 탐색을 다 마치고
        // 팀 배정을 받을 수 없다고 판단이 내려진 것들도 배정완료로 체크
        done[v] = true;
    }
}