[백준] BOJ_9466 텀 프로젝트

이종찬·2026년 1월 13일

baekjoon

1. 문제 정보

문제 요약: 명의 학생들이 각각 프로젝트를 함께하고 싶은 학생을 한 명 선택합니다. 선택의 흐름이 자신에게 다시 돌아오는 경우(Cycle)에만 한 팀이 됩니다. 팀에 속하지 못한 학생들의 수를 구해야 합니다.

핵심 제약:

학생 수 $n$ 은 최대 $100,000$ .
시간 제한 3초.

단순한 $O(N^2)$ 탐색으로는 Time Limit Exceeded(TLE)가 발생합니다.

난이도: Gold 3
링크: https://www.acmicpc.net/problem/9466

2. 접근 방식

이 문제는 겉보기엔 단순한 구현 같지만, 방향 그래프(Directed Graph)에서의 사이클 검출(Cycle Detection) 알고리즘을 정확히 이해하고 있어야 풀 수 있습니다.

2-1. 문제의 본질: 그래프와 사이클

학생들의 선택 관계를 방향 그래프로 모델링할 수 있습니다. 각 노드(학생)는 정확히 하나의 간선(선택)을 가집니다. (Out-degree = 1)
이런 그래프의 특징은 반드시 컴포넌트 내에 하나의 사이클이 존재하며, 나머지 노드들은 그 사이클을 향해 들어가는 형태를 띱니다.

우리의 목표는 사이클에 포함된 노드의 개수를 세어, 전체 $n$ 에서 빼는 것입니다.

2-2. 알고리즘 설계: DFS와 '3-Color' 전략

단순히 visited 배열 하나만 쓰면, 이미 방문했던 노드가 이번 탐색 경로상의 사이클인지, 아니면 이전의 다른 탐색에서 끝난 노드인지 구분할 수 없습니다.

이를 해결하기 위해 노드의 상태를 3단계로 관리해야 합니다.

방문 안 함: 아직 탐색하지 않음.
방문 중 (visited = true, finished = false): 현재 재귀 스택(Stack)에 들어있는 상태. 탐색이 진행 중임.
탐색 완료 (finished = true): 더 이상 볼 필요가 없는 상태. 사이클 여부 판별이 끝남.

만약 탐색 중 visited가 true인데 finished가 false인 노드를 다시 만났다면?
"현재 경로에서 다시 돌아왔다"는 뜻이므로 사이클(Cycle)이 발생한 것입니다.

2-3. 수식 및 시간 복잡도

모든 노드는 정답 코드 기준으로 dfs를 통해 단 한 번씩만 호출됩니다.

노드 방문: $O(V)$

간선 확인: $O(E)$

여기서 $V=N, E=N$ 이므로, 총 시간 복잡도는 $O(N)$ 입니다.

이전의 실패 코드처럼 $O(N^2)$ 이 되면 $N=100,000$ 일 때 약 100억 번의 연산이 필요해 시간 초과가 발생합니다.

3. 코드 구현

3-1. 실패한 코드 (시간 초과)

처음에는 단순한 DFS/백트래킹 방식으로 접근했습니다. isCycle 함수 내에서 visit 배열을 초기화하거나, 이미 탐색한 경로를 중복해서 탐색하는 구조적인 문제가 있었습니다.

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int T;

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            int[] stu = new int[n + 1];
            boolean[] visit = new boolean[n + 1];
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                stu[j] = Integer.parseInt(st.nextToken());
            }
            int answer = solv(n, stu, visit);
            sb.append(answer).append('\n');
        }

        System.out.println(sb);
    }

    private static int solv(int n, int[] stu, boolean[] visit) {
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            if (!visit[i]) {
                // 매번 새로운 탐색을 시도하며 중복 연산 발생 가능성 높음
                if (!isCycle(i, stu, visit))
                    answer += 1;
            }
            visit[i] = true;
        }
        return answer;
    }

    private static boolean isCycle(int target, int[] stu, boolean[] visit) {
        List<Integer> list = new ArrayList<>();
        int next = stu[target];
        while (!visit[next]) {
            visit[next] = true; // 방문 처리

            if (target == next)
                return true;

            list.add(next);
            next = stu[next];
        }

        // 여기서 visit을 다시 false로 돌리는 백트래킹 로직이 최악의 경우 O(N^2)을 유발
        for (int n : list) {
            visit[n] = false;
        }

        return false;
    }
}

3-2. 정답 코드 (DFS + finished 배열 최적화)

finished 배열을 추가하여, 이미 검증이 끝난 노드는 다시 보지 않도록 최적화했습니다.

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int T;
    static int[] stu;
    static boolean[] visit;    // 방문 여부 확인
    static boolean[] finished; // 탐색 종료 여부 확인 (핵심)
    static int count;          // 사이클에 속한 노드 수

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            stu = new int[n + 1];
            visit = new boolean[n + 1];
            finished = new boolean[n + 1];
            count = 0;

            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                stu[j] = Integer.parseInt(st.nextToken());
            }

            // 모든 노드에 대해 DFS 수행
            for (int j = 1; j <= n; j++) {
                if (!visit[j])
                    dfs(j);
            }
            // 전체 학생 수 - 사이클에 속한 학생 수 = 팀 없는 학생 수
            sb.append(n - count).append('\n');
        }

        System.out.println(sb);
    }

    private static void dfs(int now) {
        visit[now] = true;
        int next = stu[now];

        if (!visit[next]) {
            // 다음 노드를 아직 방문하지 않았다면 깊게 탐색
            dfs(next);
        } else {
            // 다음 노드를 방문했는데, 아직 '탐색 종료(finished)' 상태가 아니라면?
            // -> 사이클 발견!
            if (!finished[next]) {
                // 사이클 내부의 노드 개수 카운트
                count += 1;
                while (next != now) {
                    next = stu[next];
                    count += 1;
                }
            }
        }

        // 현재 노드 탐색 종료 처리
        finished[now] = true;
    }
}

4. 회고 및 배운 점

4-1. 실패 원인 분석: 시간 복잡도

실패한 코드에서 가장 치명적인 부분은 isCycle 메서드 끝부분의 visit[n] = false 초기화 로직입니다.

이는 경로를 탐색했다가, 사이클이 아니면 방문 기록을 지워버리는 방식입니다.
이렇게 되면 이미 검사했던 경로를 다른 노드에서 출발할 때 또 다시 중복 검사하게 됩니다.

최악의 경우(한 줄로 길게 이어진 $1 \to 2 \to \dots \to N$ 그래프) 시간 복잡도가 $O(N^2)$ 까지 치솟게 됩니다.

4-2. 해결

정답 코드는 finished 배열을 도입하여 이를 해결했습니다.

finished[node] = true는 "이 노드로부터 시작되는 사이클 확인과 처리가 완전히 끝났다"는 의미입니다.
따라서 finished가 true인 노드는 어떤 경우에도 재방문하거나 재연산하지 않습니다.
이 기법을 통해 모든 노드와 간선을 선형 시간() 내에 처리할 수 있습니다.

4-3. 구현 디테일

사이클을 발견했을 때, 단순히 true만 반환하는 것이 아니라 사이클을 구성하는 노드의 개수를 세야 합니다.
while (next != now) 루프를 통해, 사이클의 시작점(next)이 다시 현재 노드(now)로 돌아올 때까지 순회하며 count를 증가시키는 로직이 매우 중요합니다.