백준 9466. 텀 프로젝트

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

처음의 시간초과 풀이

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input()) # 학생 수
    students = list(map(int,input().split())) # 선택한 학생들의 번호(학생 인덱스는 1부터 시작)
    students = [s - 1 for s in students]
    ans = 0 # 프로젝트 팀에 속하지 못한 학생들의 수

    def dfs(start):
        global lst
        nxt = students[start]

        if nxt == start:
            students[nxt] = -1
            return

        if nxt in lst:
            for l in lst:
                students[l] = -1
            return

        if not visited[nxt]:
            visited[nxt] = 1
            lst.append(nxt)
            dfs(nxt)


    for i in range(n):
        visited = [0] * n

        if students[i] == -1:
            continue

        lst = [i]
        dfs(i)

    for student in students:
        if student >= 0:
            ans += 1

    print(ans)

---

import sys

sys.setrecursionlimit(10**6) 
input = sys.stdin.readline

def dfs(node):
    global count
    visited[node] = 1  # 방문 처리
    cycle.append(node)  # 현재 탐색 경로 저장
    nxt = students[node]

    if not visited[nxt]:  # 방문하지 않은 경우 계속 탐색
        dfs(nxt)
    elif not finished[nxt]:  # 방문했지만, 아직 DFS 종료되지 않은 경우 → 사이클 발견
        cycle_idx = cycle.index(nxt)  # 사이클이 시작되는 위치
        count += len(cycle[cycle_idx:])  # 사이클에 속한 학생 수 증가

    finished[node] = 1  # DFS 탐색 완료 처리


t = int(input())
for _ in range(t):
    n = int(input())
    students = list(map(lambda x: int(x) - 1, input().split()))  # 0-based 인덱스로 변환

    visited = [0] * n
    finished = [0] * n  # DFS 종료 여부 기록
    count = 0  # 사이클에 포함된 학생 수

    for i in range(n):
        if not visited[i]:  # 방문하지 않은 노드에서 DFS 시작
            cycle = []  # 현재 탐색 경로 저장
            dfs(i)

    print(n - count)  # 팀을 이루지 못한 학생 수 출력

[체크 포인트]

1. dfs를 최소로 실행, visited배열도 하나만 사용

2. finished 배열로 해당 노드로 시작할 때 사이클 유무를 판단할 수 있게 기록

3. 사이클이 없다....나중에 발견할 수 있으니까 사이클 시작되는 위치 정확히 index 찾아서 거기부터 끝까지 길이 count에 더함. (count는 팀 이룬 학생들 변수)