#382 백준 파이썬 [9466] 텀 프로젝트 - DFS

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

 

SOLUTION

https://claude-u.tistory.com/434 10451 순열 사이클 문제와 굉장히 유사하다.

풀이도 위 하이퍼링크를 참조하자.

다른 점은 조건에 '반드시 team의 마지막 학생은 team의 첫 학생을 지목해야한다는 것'이다.

즉 팀이 결성 되기 위해선 첫과 끝이 이어진 순환 사이클이 되어야한다.

따라서 위와 같은 사이클에서는 5가 빠지고 1,2,3,4만이 팀이 구성된다.

따라서 하단의 result += cycle[cycle.index(number):] 라는 코드를 통해 사이클이 되는 구간부터만 팀을 구성하게 한다.

마지막 팀원이 가리키는 팀원이 첫 팀원이 되는 것이다.

PYTHON CODE

import sys
sys.setrecursionlimit(111111) #충분한 재귀 깊이를 주어 오류를 예방


def dfs(x):
    global result
    visited[x] = True
    cycle.append(x) #사이클을 이루는 팀을 확인하기 위함
    number = numbers[x]
    
    if visited[number]: #방문가능한 곳이 끝났는지
        if number in cycle: #사이클 가능 여부
            result += cycle[cycle.index(number):] #사이클 되는 구간 부터만 팀을 이룸
        return
    else:
        dfs(number)


for _ in range(int(input())):
    N = int(input())
    numbers = [0] + list(map(int, input().split()))
    visited = [True] + [False] * N #방문 여부
    result = []
    
    for i in range(1, N+1):
        if not visited[i]: #방문 안한 곳이라면
            cycle = []
            dfs(i) #DFS 함수 돌림
            
    print(N - len(result)) #팀에 없는 사람 수