boj.kr/9466 팀 프로젝트 (gold3) 파이썬 풀이

1. 인덱스 번호를 노드번호, 요소 값을 선택한 노드번호로 갖도록 choose 리스트를 N+1 길이로 초기화

2. chk 리스트를 N+1 개의 0으로 초기화

3. team 리스트를 생성

4. 1번부터 N번 노드까지 순회하면서 아래를 반복

4.1. chk[번호] 값이 0인지 검사

4.2. chk[번호] 값이 0이면, cycle 리스트를 초기화하고 dfs(번호)를 호출

4.2.1. dfs(번호)를 다음과 같이 실행

4.2.1.1. global team 변수를 선언, chk[번호]를 1 증감, cycle에 번호를 append, nxt에 choos(번호)를 저장

4.2.1.2. chk[nxt]가 1이면, cycle에 nxt가 있는지 검사하고 있으면 cycle에서 nxt가 처음 발견되는 index부터 마지막까지 슬라이스하여 team에 추가

4.2.1.3. chk[nxt]가 1이 아니면, dfs(nxt)를 호출

5. N에서 team의 길이를 차감한 값을 출력

 

import sys
sys.setrecursionlimit(10**9)
def dfs(cur):
    global team
    chk[cur] += 1
    cycle.append(cur)
    nxt = choose[cur]
    if chk[nxt] == 1:
        if nxt in cycle:
            team += cycle[cycle.index(nxt):]
    else:
        dfs(nxt)

T = int(input())
for _ in range(T):
    N = int(input())
    choose = [0] + list(map(int, input().split()))
    chk = [0] * (N+1)
    team = []
    for node in range(1, N+1):
        if chk[node] == 0:
            cycle = []
            dfs(node)
    print(N-len(team))

 

체크 배열과 사이클 배열을 사용하지 않고 풀이하면 시간초과가 발생할 수 있다.