[백준/bfs] 11725번: 트리의 부모 찾기

-문제: https://www.acmicpc.net/problem/11725

채점까지 오래걸렸던 문제.

스스로 풀이 없이 푼 문제다 

처음에 dfs로 풀다가 setrecursionlimit(100000)까지 걸었는데 70몇퍼에서 recursionerror가 발생했다

그래서 bfs로 바꿨더니 맞은 문제

silver level2 문제 

 

-정답풀이:

from collections import deque

n=int(input())
graph=[[] for _ in range(n+1)]
ans=[0]*(n+1)

#그래프 정리 
for _ in range(n-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
visit=[0]*(n+1)    

def bfs(v):
    queue=deque()
    queue.append(v)
    visit[v]=1
    while queue:
        x=queue.popleft()
        for i in graph[x]:
            if not visit[i]:
                visit[i]=1
                queue.append(i)
                ans[i]=x
                
bfs(1)            
for i in range(2,n+1):
    print(ans[i])

-RecursionError 발생