[백준/Python] BOJ 11725 - 트리의 부모 찾기

👀 문제

11725번: 트리의 부모 찾기 ✨ 실버 2

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

🔑 키포인트

dfs

✍️ 코드

import sys
sys.setrecursionlimit(10**9)

N = int(input())
graph = [[] for _ in range(N+1)]
parents = [0 for _ in range(N+1)]

for _ in range(N-1):
    i, j = map(int, input().split())
    # 양방향으로 추가해 주기
    graph[i].append(j)
    graph[j].append(i)

def dfs(root):
    for node in graph[root]:
        if parents[node] == 0:
            parents[node] = root
            dfs(node)

dfs(1)

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

🚑 메모리 초과 발생 원인

런타임 에러 (RecursionError)가 발생했는데 이는 재귀와 관련된 에러다. 가장 많이 발생하는 이유는 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때이다.

이를 해결하기 위해서는

import sys
sys.setrecursionlimit(10**9)

재귀의 깊이 제한을 늘려주는 위 코드를 추가해 주면 된다.