오답 코드 (재귀로 DFS)

import sys
input = sys.stdin.readline

n = int(input())
tree = {i:[] for i in range(1,n+1)}
for _ in range(n-1):
    first, second = map(int, input().split())
    tree[first].append(second)
    tree[second].append(first)

# 부모 노드를 찾기
parents = {i:-1 for i in range(1,n+1)}
visited = {i:False for i in range(1,n+1)}

def write_parent(current,parent):
    # parents노드에 현재 노드의 부모 노드를 기록한다.
    parents[current]=parent
    visited[current]=True

    # 현재 노드의 연결 노드를 반복문으로 꺼낸다.
    for linked_node in tree[current]:
        # 부모 노드를 뭐로 정해야할까? parents[current]인가? parent인가?
        # 재귀를 사용한다면 parent로 해야할 것 같은데?

        # 꺼낸 노드에서 부모 노드가 아니면 재귀적으로 다음 부모 노드를 기록하도록 한다.
        if linked_node != parent and not visited[linked_node]:
            write_parent(linked_node, current)

write_parent(1,0)

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

발생한 에러

-> RecursionError가 발생했다.

RecursionError 발생 원인

재귀함수로 문제를 푸는데 시스템이 허용하는 양보다
재귀를 더 많이해서 발생한 문제이다.

부모 노드를 구하는 write_parent 함수에서
DFS를 재귀가 아닌 반복문으로 구현해야 풀 수 있을 것으로 보인다.

정답 코드 (반복문으로 DFS)

-> 재귀가 아닌 다른 방식으로 구현했다.

import sys
input = sys.stdin.readline

n = int(input())
tree = {i:[] for i in range(1,n+1)}
for _ in range(n-1):
    first, second = map(int, input().split())
    tree[first].append(second)
    tree[second].append(first)

# 부모 노드를 찾기
parents = {i:-1 for i in range(1,n+1)}
visited = {i:False for i in range(1,n+1)}

def write_parent(start):
    # parents노드에 현재 노드의 부모 노드를 기록한다.
    parents[start]=0
    stack = [start]
    visited = [False]*(n+1)

    while stack:
        # pop으로 현재 노드를 꺼내 current에 저장한다.
        current = stack.pop()
        
        # 현재 꺼낸 노드의 연결 노드를 구한다.
        for node in tree[current]:
            if not visited[node]:
                stack.append(node)
                parents[node]=current
                visited[current] = True

write_parent(1)

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