BOJ - 11725. 트리의 부모 찾기

9545 단어 백준파이썬백준

📌 런타임 에러 코드

import sys
input = sys.stdin.readline

def find(n):
    for i in tree[n]:
        if parent[i] == 0:
            parent[i] = n
            find(i)

N = int(input())
tree = [[] for _ in range(N + 1)]
# 부모 노드 저장
parent = [0 for _ in range(N + 1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

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

재귀로 풀었더니 런타임에러가 났다. 재귀 최대깊이 초과로 인한 문제같아서 다른 방식으로 풀기로 했다.

✨통과한 코드

import sys
input = sys.stdin.readline

def find(n):
    stack = [n]
    while stack:
        node = stack.pop()
        for i in tree[node]:
            if parent[i] == 0:
                parent[i] = node
                stack.append(i)

N = int(input())
tree = [[] for _ in range(N + 1)]
# 부모 노드 저장
parent = [0 for _ in range(N + 1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

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

stack에 담고 pop하는 방식으로 풀었더니 통과가 됐다!
dfs, bfs 다 상관없지만 재귀는 최대깊이 조심!

좋은 웹페이지 즐겨찾기