[10451] 순열 사이클 in python

처음엔 dfs 를 떠올리지 않고

반복문만으로 해결하려고 했으나,,

하다보니 재귀로 하는 게 더 편할 것 같아서

노선 변경!!

 

 

런타임 에러가 나서

sys.setrecursionlimit(2000)으로

최대 재귀를 늘려주었더니 해결!

 

dfs 를 이용해서 문제를 풀어주었음!

 

visited는 방문한 노드의 리스트를 저장해두는 리스트

circle은 현재 서클에 해당하는 리스트

import sys
sys.setrecursionlimit(2000)

for _ in range(int(input())):
    n = int(input())
    array = list(map(int, input().split()))
    array.insert(0,0)
    visited = set()
    answer = 0
    idx = 1


    def dfs(node, circle):
        global answer
        if node in circle:
            answer += 1
            return
        if node in visited:
            return
        visited.add(node)
        circle.add(node)
        dfs(array[node],circle)
        circle.remove(node)

    for i in range(1,n+1):
        dfs(array[i], set())

    print(answer)