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

DFS 풀이(시간초과)

import sys
sys.setrecursionlimit(100000)

n = int(input())
tree = [[] for _ in range(n+1)]
visited = [0] * (n+1)
for _ in range(n-1):
    node1,node2 = map(int,input().split())
    tree[node1].append(node2)
    tree[node2].append(node1)

node = {}
def dfs(v):
    global node
    visited[v] = 1
    

    for i in tree[v]:
        
        if visited[i] == 0:
            node[i] = v
            dfs(i)

    return node            

dfs(1)        
node = dict(sorted(node.items(),key = lambda x : x[0])    )
for i in node.values():
    print(i)

BFS 풀이

from collections import deque

n = int(input())
tree = [[] for _ in range(n+1)]
visited = [0] * (n+1)
for _ in range(n-1):
    node1,node2 = map(int,input().split())
    tree[node1].append(node2)
    tree[node2].append(node1)

visited = [0] * (n+1)

def bfs(v):
    
    queue = deque()
    queue.append(v)
    
    while queue :
        
        v = queue.popleft()
        
        for i in tree[v]:
            if visited[i] == 0:
                queue.append(i)
                visited[i] = v

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