[백준] 9466번 텀 프로젝트 - 파이썬/DFS

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

import sys
sys.setrecursionlimit(10**6)

T = int(input())

for t in range(T):


    N = int(input())
    fir = [ i for i in range(1,N+1) ]
    sec = list(map(int,input().split()))

    ans_list = []

    def dfs(x,visited):

        global ans_list

        visited[x-1] = True

        route.append(x)

        if visited[sec[x-1]-1]:
            if sec[x-1] in route:
                ans_list += route[ route.index(sec[x-1]) : ]

            return

        else:
            dfs(sec[x-1],visited)

    visited = [False]*N

    for i in range(1,N+1):
        if not visited[i-1]:
            route=[]
            dfs(i,visited)

    print(N-len(ans_list))

방문 루트를 작성하고 다음 방문노드가 해당 루트에 있으면 정지한다.

주의할점은 모든 루트를 저장하는 것이 아니고 반복되는 구간만 저장하는 것이다.

루트를 슬라이싱해서 반복되는 구간을 구할 수 있다.