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

 

DFS하니까 재귀에러나고 시간초과 메모리초과 가관이어서 

BFS로 다시 풀었다.

구조는 똑같이 queue에 1을 넣고 1부터 위에서 아래로 탐색하며 parent값을 자식들에게 할당하는 방식.

import sys
input = sys.stdin.readline
from collections import defaultdict,deque

N = int(input())
graph = defaultdict(list)

for _ in range(N-1):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

queue = deque([1])
ans = {}
check = [False for _ in range(N+1)]

while queue:
    parent = queue.popleft()
    for i in graph[parent]:
        if not check[i]:
            ans[i] = parent
            queue.append(i)
            check[i] = True

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