백준 10451 "텀 프로젝트" (JAVA)

🔍 문제링크

https://www.acmicpc.net/problem/9455

---

📌 문제 요약

• 각 학생들은 프로젝트 팀을 구성할 때,자신이 원하는 단 한 명의 학생만 선택할 수 있다.
• 팀을 이루는 경우는 사이클(Cycle)이 형성된 경우이다.
• 팀을 이루지 못한 학생의 수를 출력해야 한다.

---

🛠 풀이 및 알고리즘

1️⃣ DFS를 활용한 사이클 탐색

• 각 학생이 가리키는 관계를 DFS를 통해 따라가면서 방문 여부를 체크
• DFS 탐색 중 방문했던 노드를 다시 방문하면 사이클이 형성된 것

2️⃣ 방문 체크(visited)와 종료 체크(finished) 배열 활용

• `visited[now] = 1` : 현재 학생 방문 체크
• `finished[now] = 1` : 현재 학생이 속한 탐색이 종료
• 사이클을 확인하는 조건
  • `visited[next] == 1 && finished[next] == 0` : 방문한적은 있지만, 끝난적은 없는경우 사이클 발생
  • 이 경우, 사이클을 이루고 있는 학생들을 하나씩 세며 cnt++

---

💡 코드

public class Baekjoon_9466 {
    static int n, cnt;
    static int[] nums;
    static int[] visited;
    static int[] finished;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            nums = new int[n + 1];
            visited = new int[n + 1];
            finished = new int[n + 1];
            cnt = 0;
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n; i++) {
                nums[i] = Integer.parseInt(st.nextToken());
            }
            for (int i = 1; i <= n; i++) {
                if (visited[i] == 0) {
                    dfs(i);
                }
            }
            sb.append(n - cnt).append('\n');
        }
        System.out.println(sb);
    }

    static void dfs(int now) {
        visited[now] = 1;
        int next = nums[now];

        if (visited[next] == 0) { // 아직 방문하지 않은 경우 탐색 진행
            dfs(next);
        } else if (finished[next] == 0) {  // 방문한 적은 있지만 탐색이 끝나지 않은 경우 (사이클 발생)
            int temp = next;
            cnt++;
            while (temp != now) { // 사이클을 이루는 학생 수를 카운트
                temp = nums[temp];
                cnt++;
            }
        }
        finished[now] = 1; // 현재 학생의 탐색 완료
    }
}

---

🏆 시간 복잡도 분석

• 각 숫자는 한 번씩만 방문하므로, 한 사이클을 찾는 DFS 탐색은 O(N)
• 전체 테스트 케이스 T개에 대해 반복되므로 최대 O(T * N)
• N ≤ 1,000 이므로  최악의 경우 O(TN) = O(T * 1,000,000 ) 연산.