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

문제 설명

 

입출력 예제

 

---

풀이 코드

위 예시를 그림으로 표현하면 다음과 같다.

4, 6, 7은 하나의 프로젝트 팀, 싸이클을 이루고, 3은 자기 자신을 선택해 자기 자신만 프로젝트 팀에 속한다. 

총 학생의 수는 7명이므로 프로젝트 팀을 이루고 있는 (3) 그룹과 (4, 6, 7)을 빼면 어느 프로젝트 팀에도 속하지 않는 학생 수는 3이 된다.

 

정답 코드

import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

def dfs(start):
    global cnt
    visited[start] = True
    route.append(start)

    next = graph[start]
    if visited[next]: # 사이클이 되는 팀을 뺌
        if next in route:
            cnt -= len(route[route.index(next):])
        return
    else: # 방문하지 않았다면 다음을 탐색
        dfs(next)
            
T = int(input())

for _ in range(T):
    n = int(input())

    graph = [0] + list(map(int, input().split()))

    visited = [False] * (n + 1)
    cnt = n

    for i in range(1, n + 1): # 1번 학생부터 탐색 시작
        if not visited[i]:
            route = []
            dfs(i)

    print(cnt)