BOJ_9466_텀 프로젝트_java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 백준 9466번 텀프로젝트
 골드 3
 */
public class BOJ_9466_텀프로젝트 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc<=T; tc++){
            int n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int[] choice = new int[n+1];
            int[] vistied = new int[n+1]; // -1: 사이클 생성 불가능, 0: 방문 안함, 1: 방문함, 2: 팀 구해짐
            for (int i = 1; i<=n; i++){
                choice[i] = Integer.parseInt(st.nextToken());
                if (choice[i]==i) vistied[i] = 2; // 사이클이 생성되는 경우 (자기 자신)
            }
            for (int i = 1; i<=n; i++){
                if (vistied[i] != 2 || vistied[i] != -1){ // 가능성 있는 것만 조사
                    dfs(n, choice, i, new ArrayList<>(), vistied);
                }
            }
            int cnt = 0;
            for (int i = 1; i<=n; i++){
                if (vistied[i] != 2) cnt++; // 팀 안구해진 사람 체크
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb.toString());
    }

    public static void dfs(int n, int[] choice, int student, List<Integer> selected, int[] vistied){
        selected.add(student);
        if (vistied[student] == 1){ // 탐색 종료 지점
            int selectedListSize= selected.size();
            for (int i = 0; i<selectedListSize-1; i++){
                int nowStudent = selected.get(i);
                if (nowStudent == student){ // 사이클 확인
                    for (int j = 0; j<i; j++){
                        vistied[selected.get(j)] = -1; // 사이클 생성 불가능
                    }
                    for (int j = i; j<selectedListSize-1; j++){ // 팀 구성 체크
                        vistied[selected.get(j)] = 2; // 팀 완료
                    }
                    break;
                }else {
                    vistied[nowStudent] = 0; // 방문 초기화
                }
            }
        }else if (vistied[student] == 0){ // 아직 방문 안한 경우
            vistied[student] = 1;
            dfs(n, choice, choice[student], selected, vistied);
        }else if(vistied[student] == -1 || vistied[student] == 2){ // 사이클 불가능
            int selectedListSize= selected.size();
            for (int i = 0; i<selectedListSize-1; i++){
                int nowStudent = selected.get(i);
                vistied[nowStudent] = -1;
            }
        }
    }
}​

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 백준 9466번 텀프로젝트
 골드 3
 */
public class BOJ_9466_텀프로젝트 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc<=T; tc++){
            int n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int[] choice = new int[n+1];
            int[] vistied = new int[n+1]; // -1: 사이클 생성 불가능, 0: 방문 안함, 1: 방문함, 2: 팀 구해짐
            for (int i = 1; i<=n; i++){
                choice[i] = Integer.parseInt(st.nextToken());
                if (choice[i]==i) vistied[i] = 2; // 사이클이 생성되는 경우 (자기 자신)
            }
            for (int i = 1; i<=n; i++){
                if (vistied[i] != 2 || vistied[i] != -1){ // 가능성 있는 것만 조사
                    dfs(n, choice, i, new ArrayList<>(), vistied);
                }
            }
            int cnt = 0;
            for (int i = 1; i<=n; i++){
                if (vistied[i] != 2) cnt++; // 팀 안구해진 사람 체크
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb.toString());
    }

    public static void dfs(int n, int[] choice, int student, List<Integer> selected, int[] vistied){
        selected.add(student);
        if (vistied[student] == 1){ // 탐색 종료 지점
            int selectedListSize= selected.size();
            for (int i = 0; i<selectedListSize-1; i++){
                int nowStudent = selected.get(i);
                if (nowStudent == student){ // 사이클 확인
                    for (int j = 0; j<i; j++){
                        vistied[selected.get(j)] = -1; // 사이클 생성 불가능
                    }
                    for (int j = i; j<selectedListSize-1; j++){ // 팀 구성 체크
                        vistied[selected.get(j)] = 2; // 팀 완료
                    }
                    break;
                }else {
                    vistied[nowStudent] = 0; // 방문 초기화
                }
            }
        }else if (vistied[student] == 0){ // 아직 방문 안한 경우
            vistied[student] = 1;
            dfs(n, choice, choice[student], selected, vistied);
        }else if(vistied[student] == -1 || vistied[student] == 2){ // 사이클 불가능
            int selectedListSize= selected.size();
            for (int i = 0; i<selectedListSize-1; i++){
                int nowStudent = selected.get(i);
                vistied[nowStudent] = -1;
            }
        }
    }
}