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

문제 링크

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

풀이 

- bfs 풀이 

- graph[] 에 연결된 노드 번호 기록 

- root 노드인 1부터 시작하여 노드 방문 시 answer에 이전 노드 번호 기록 

from collections import deque 

def bfs(x):
  visited[x] = True
  q = deque()
  q.append(x)

  while q:
    a = q.popleft()
    for i in graph[a]:
      if not visited[i]:
        answer[i] = a
        visited[i] = True
        q.append(i)
  
n = int(input())

graph = [ [] for _ in range(n+1)]
# 방문 표시 
visited = [False] * (n+1)
# 이전 방문 노드 기록 
answer = [0] * (n+1)

# 연결된 노드 번호 기록
for _ in range(n-1):
  a, b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)

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