[BOJ]9466 - 텀 프로젝트(G3)

문제 링크

9466-텀 프로젝트

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다.
각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

문제 풀이

한 번 방문한 곳은 visited, 검사가 끝난곳은 finish 로 표시할 때

visited 이지만, finish 아니라면
이미 방문한 곳을 또 방문했다는 의미여서 사이클 생성
팀 편성 성공한 학생 수 +1 해주고 finish 처리

visited 도 아니고, finish 도 아니라면
처음 방문하는 곳이기때문에 방문 처리해주고 재귀로 더 확인

사이클인 애들은 재방문하면서 finish 처리를 해줄 수 있지만
사이클이 아닌 애들은 불가능하기때문에
따로 재귀에서 빠져나와서 finish 처리를 해준다

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

public class Main {

    static int N, cnt;
    static int[] students;
    static boolean[] finish, visited;

    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());
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());

            students = new int[N + 1];
            visited = new boolean[N + 1];
            finish = new boolean[N + 1];
            cnt = 0;

            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                students[i] = Integer.parseInt(st.nextToken());
            }

            for (int i = 1; i <= N; i++) {
                if(!finish[i]) dfs(i);
            }
            sb.append(N - cnt);
            sb.append("\n");
        }
        System.out.println(sb);

    }

    static void dfs(int n) {
    
    	// 이미 방문한 노드라면
        // 팀 편성 완료 & 팀 편성 인원 증가
        if (visited[n]) { 
            finish[n] = true;
            cnt++;
        } else {
            visited[n] = true;
        }

		// 내가 가리키는 학생이 아직 팀 결성을 못한 경우
        if (!finish[students[n]]) {
            dfs(students[n]);
        }
        visited[n] = false;
        finish[n] = true;
    }
}

시간 초과때문에 애 좀 먹었지만
그래도 되게 어려운건 아닌듯한 문제