[Python] 백준(BOJ) 9466번: 텀 프로젝트 - 스택, dfs

문제

9466번: 텀 프로젝트

풀이

재귀를 사용하는 방법이기 때문에 recursion limit을 충분히 설정해주지 않으면 런타임에러가 난다.

스택과 dfs를 사용해서 풀었는데 조금 더 효율적인 방법이 있을것 같다.  

import sys
sys.setrecursionlimit(10**8)

# 테스트 케이스 개수
T = int(sys.stdin.readline())

def dfs(i):
    stack.append(i)

    # 아직 방문 안했으면
    if visited[students[i]] == 0:
        visited[students[i]] = 1
        dfs(students[i])

    # 방문한애를 만나면 (싸이클)
    elif visited[students[i]] == 1:
        flag = 0

        while stack:
            now = stack.pop()

            if now != students[i] and flag == 0:
                visited[now] = 2
            elif now == students[i]:
                visited[now] = 2
                flag = 1
            else:
                visited[now] = -1

    else:
        while stack:
            now = stack.pop()
            visited[now] = -1


# 각 테스트케이스마다
for _ in range(T):
    # 학생의 수
    n = int(sys.stdin.readline())

    # 방문 배열
    visited = [0 for _ in range(n+1)]

    # 선택한 사람
    students = list(map(int, sys.stdin.readline().split(" ")))
    students.insert(0, 0)

    stack = []
    for i in range(1, n+1):
        if visited[i] == 0:
            visited[i] = 1
            dfs(i)

    count = 0
    for each in visited:
        if each == -1:
            count += 1
    print(count)