[BOJ]-9466 텀프로젝트

📃 텀프로젝트

DFS를 활용해서 사이클 여부를 판단해야 하는 문제였다.
재귀를 통해 DFS를 구현했다.

코드

# 텀 프로젝트
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
t = int(input())

def dfs(i):
    cycle.append(i)
    global result 
    visited[i] = True 
    if visited[student[i]]:
        if student[i] in cycle :
            result += cycle[cycle.index(student[i]):]
            return 
    else : 
        dfs(student[i])




for i in range(t):
    
    n =int(input())
    visited = [False] * (n+1)
    student = [0] + list(map(int,input().split()))
    result = [] 

    for i in range(1,n+1):
        if visited[i] == False : 
            cycle = []
            dfs(i)
    print(n-len(result)) 

풀이

sys.setrecursionlimit(10000000)

• 재귀를 사용해서 풀어야 하는 문제일 때 필수
• 파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕은 편이다. 따라서 재귀로 문제를 풀 경우 드물지 않게 이 제한에 걸리게 되므로 setrecursionlimit을 늘려줘야 한다.

기억해야겠다.

cycle[cycle.index(student[i]):]

• student[i] 값을 가진 인덱스 추출

이 코드가 이해가 안 돼서 test case 를 작성해 보았다.

cycle = [1,1,3,4,5,6]

result = cycle[cycle.index(3):]
print(cycle.index(3))
result1 = cycle[2:]
print(result)
print(result1)

출력 결과

2
[3, 4, 5, 6]
[3, 4, 5, 6]