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

---

1. 메모리 초과 코드

import sys
from collections import defaultdict


def dfs(key, cycle):
    visited[key] = True
    if visited[d[key]]:
        if d[key] in cycle:
            left = cycle.index(d[key])
            result.extend(cycle[left:])
    else:
        dfs(d[key], cycle + [d[key]])

answer = []
sys.setrecursionlimit(200000)
T = int(sys.stdin.readline().rstrip())
for _ in range(T):
    n = int(sys.stdin.readline().rstrip())
    nums = list(map(int, sys.stdin.readline().rstrip().split()))

    d = defaultdict(int)
    for i in range(1, n + 1):
        d[i] = nums[i - 1]

    result = []
    visited = [False] * (n+1)
    for start in range(1, n + 1):
        if not visited[start]:
            dfs(start, [start])
    print(n-len(result))

2. 정답 코드

import sys
from collections import defaultdict


def dfs(key, cycle):
    visited[key] = True
    if visited[d[key]]:
        if d[key] in cycle:
            left = cycle.index(d[key])
            result.extend(cycle[left:])
    else:
        cycle.append(d[key])
        dfs(d[key], cycle)

answer = []
sys.setrecursionlimit(200000)
T = int(sys.stdin.readline().rstrip())
for _ in range(T):
    n = int(sys.stdin.readline().rstrip())
    nums = list(map(int, sys.stdin.readline().rstrip().split()))

    d = defaultdict(int)
    for i in range(1, n + 1):
        d[i] = nums[i - 1]

    result = []
    visited = [False] * (n+1)
    for start in range(1, n + 1):
        if not visited[start]:
            dfs(start, [start])

    answer.append(n-len(result))

for i in answer:
    print(i)

2. 후기

dfs(d[key], cycle + [d[key]]) 이 부분이 메모리 초과의 원인이다.
+를 통해 생성된 새로운 사이클은 새로운 id를 할당받는다.

반면에 append()를 사용할 경우 동일한 id를 사용하기 때문에 새로운 메모리 공간이 필요없다.

아래 블로그에서 도움을 받았다.

• https://claude-u.tistory.com/435