[Python] BOJ / 9466번 / 텀 프로젝트

9466번: 텀 프로젝트

---

📝 풀이

• 팀이 만들어지기 위해선 사이클의 마지막 학생이 선택한 학생이 첫 번째 학생과 같아야 한다. 즉, 첫과 끝이 이어진 순환 사이클이 형성되어야 한다.
  • result += cycle[cycle.index(arr[x]):]
  • 위 연산을 통해 순환 사이클이 형성되는 구간부터만 팀을 구성시킬 수 있다.

---

💻 소스 코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def dfs(x):
    global result

    visited[x] = True
    cycle.append(x) #현재까지의 사이클에 포함되는 학생 저장

    if visited[arr[x]]: #방문할 수 있는 곳을 모두 방문한 경우
        if arr[x] in cycle: #사이클이 가능한지 확인
            result += cycle[cycle.index(arr[x]):]   # 사이클이 형성되는 구간부터만 팀으로 구성
    else: dfs(arr[x])

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

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

    print(n - len(result))