[PyPy3] setrecursionlimit(10**6)이 메모리 초과일 때 해결책

백준에서 문제를 풀 때,
Python 3보다 PyPy3가 빠르다고 해서 대부분 PyPy3으로 문제를 제출한다.

하지만 DFS 등 재귀 알고리즘을 사용하는 경우에는 런타임 에러(RecursionError)가 발생하곤 한다.

PyPy3에서는 초기 재귀에 사용하는 스택 메모리가 제한되어 있어 재귀 횟수가 제한되어 있으며, 초기값은 1000번이다. (링크)

이럴 때 해결방법으로 setrecursionlimit(10**6)과 같이 적당히 큰 수를 입력해주면 재귀 메모리를 늘려 재귀 횟수 제한을 풀 수 있는데, 무작정 큰 수를 대입하면 오히려 메모리 초과가 발생할 수 있다.

백준 11725. 트리의 부모 찾기

DFS를 통해 문제를 해결해야 하며,
setrecursionlimit을 사용하지 않으면 런타임 에러(RecursionError)가 발생한다.

# 트리를 양방향 그래프처럼 표현(무방향이기 때문에)
# 1에서 시작해서 DFS로 탐색을 진행
# 1이 root이므로, 직전 노드는 반드시 부모가 될 수밖에 없음. 
# 모든 노드에 대해서 DFS가 완료된다면 부모를 모두 찾게 됨.

# 이진 트리가 아니라서 left, right로 만들 수 없다!!!

from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)

N = int(sys.stdin.readline().rstrip())
tree = defaultdict(list)
for _ in range(N-1):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    tree[a].append(b)
    tree[b].append(a)

parents = [0] * (N+1) # visited의 역할도 병행
parents[1] = -1

def dfs(start):
    for next in tree[start]:
        if parents[next]:
            continue
        parents[next] = start
        dfs(next)

dfs(1)
for i in range(2, N+1):
    print(parents[i])

이 문제에서 sys.setrecursionlimit(10**5) 대신 10**6을 입력하면 메모리 초과가 발생한다.

메모리 초과가 발생하는 이유

아래는 스크랩 내용입니다. 원본 링크

위 문제에서 노드의 개수는 최대 100,000개다.

따라서 dfs는 최대 100,000번 진행되기 때문에 sys.setrecursionlimit(100000) 또는 sys.setrecursionlimit(10**5)만 해도 충분하다.

접근부터 틀린건가 고민하면서 질문 검색을 보니, 10**5로 바꾸면 맞는다는 답변이 있어서 바꾸어 보니 맞았다.

setrecursionlimit의 뜻이 그만큼 미리 스택 영역의 메모리를 잡아둔다는 뜻이라서 메모리 초과가 나온 거라는 안내도 있었다.