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

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

9466번: 텀 프로젝트

이 문제는 리스트를 순회하면서 몇명의 인원이 팀이 되었는지 (순환 싸이클이 완성되었는지) 판단하는 문제이다.

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

    for v in range(1, n+1):
        if not visited[v]:
            visited[v] = 1
            team = [v]

            while not visited[arr[v]]:
                v = arr[v]
                visited[v] = 1
                team.append(v)
            if arr[v] in team:
                result += team[team.index(arr[v]):]
    print(n - len(result))

앞 사람이 지목한 팀원을 계속 team에 추가해 나가다가 이미 지목됐던 사람이 지목될 경우, 가장 안쪽의 while 반복문이 종료된다.

이 때 마지막으로 지목당한 사람이 team 리스트에 있다면 그 사람부터 순환 싸이클이 시작된다는 의미이므로 이 인덱스부터 마지막 인덱스까지 result에 추가해준다.

 

최종적으로 전체 인원에서 result에 추가된 인원 수를 빼면 팀을 이루지 못한 인원 수가 나온다.