이번에 풀어본 문제는
백준 9466번 텀 프로젝트 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int answer;
    static int [] select;
    static boolean [] isDone;
    static boolean [] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while(t-- > 0)
        {
            answer = 0;
            int N = Integer.parseInt(br.readLine());
            select = new int[N+1];
            isDone = new boolean[N+1];
            visited = new boolean[N+1];

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

            for(int i = 1; i <= N; i++)
            {
                if(!isDone[i]) dfs(i);
            }
            sb.append(N-answer).append("\n");
        }
        System.out.print(sb);
    }
    static void dfs(int n)
    {
        visited[n] = true;
        int next = select[n];
        if(!visited[next]) dfs(next);
        else
        {
            if(!isDone[next])
            {
                answer++;
                isDone[next] = true;
                while(next != n)
                {
                    answer++;
                    next = select[next];
                    isDone[next] = true;
                }
            }
        }
        isDone[n] = true;
    }
}

📝 풀이

N명의 학생이 한명 씩 팀원을 지목할 때, 사이클이 형성되면 같은팀으로 간주하는 문제입니다. 자신을 선택할 수 있습니다.
한명씩만 선택할 수 있기 때문에 1차원 배열로 각 학생의 선택을 담아주고, 방문배열 두개를 활용하여 dfs탐색을 진행하면 됩니다.
방문한 노드이지만(visited) 아직 탐색이 종료되지 않았다면(!isDone) 방문의 끝, 즉 사이클이 형성된 것이므로, 선택된 사이클의 모든 팀원을 카운트해주면 됩니다.

📜 후기

조건이 간단해서 쉬울거라 생각했는데, 생각보다 많이 어려웠습니다. 두 개의 방문배열로 사이클 여부를 판단하는 것을 이해하는 데 시간이 조금 걸렸던 문제입니다.