이번 문제는 DFS를 통해 학생들 간의 사이클이 존재하는지의 여부를 확인하는 문제이다. 처음에는 dfs함수의 인자로 현재 팀에 속하기로 한 학생들의 번호를 담는 리스트를 넣고, 이를 이용하여 해당 리스트의 첫번째 인자와 현재 학생의 번호가 같을 경우 사이클이므로 팀 리스트를 순회하며 팀에 속하였다는 처리를 하도록 하였다. 답은 잘 도출되었지만, 메모리초과가 발생하였다.

그래서 다른 방법으로 사이클의 유무를 확인하였다. 학생들을 순회하며 전역 변수인 cycle리스트에 현재 학생을 넣고, 현재 학생이 가리키는 학생이 방문처리 된 경우, cycle에 가리키는 학생이 있을 경우에는 사이클로 판명되므로, cycle리스트 내의 가리키는 학생의 인덱스부터 끝까지의 원소들을 결과 리스트에 담도록 하였다. 만약 가리키는 학생이 방문되지 않았다면 dfs함수를 재귀호출 하였다. 결과적으로 결과 변수에 팀에 속하게 된 학생들만 들어가게 되므로, n-결과변수의 길이를 통해 팀에 속하지 않은 학생의 수를 도출하였다.

Code

import sys
sys.setrecursionlimit(10**6)
t = int(input())
def dfs(cur):
    chk[cur] = True
    cycle.append(cur)
    if chk[info[cur]]:
        if info[cur] in set(cycle):
            answer.extend(cycle[cycle.index(info[cur]):])
        return
    else:
        dfs(info[cur])
for _ in range(t):
    n = int(input())
    info = [0] + list(map(int, input().split()))
    chk = [False for _ in range(n+1)]
    answer = []
    for i in range(1, n+1):
        if not chk[i]:
            cycle = []
            dfs(i)
    print(n-len(answer))

같은 코드임에도 PyPy3에서는 메모리 초과가 발생하였고, Python3에서는 정답처리를 받았다. 아무래도 PyPy3가 메모리를 많이 사용하기 때문인 것으로 생각된다.