[백준/파이썬] 11725 트리의 부모 찾기

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

---

알고리즘 분류

• BFS

문제 풀이

parents리스트는 각각 노드에 대한 부모를 기록하는 리스트이다.

여기서 4번노드의 경우 1,2,7번노드와 연결되어있는데, 1번노드는 4번노드의 부모노드이기 때문에 1번노드를 제외하고 기록해준다.

소스코드

from collections import deque

n=int(input())
graph={i:[] for i in range(1,n+1)}
parents=[0]*n

for i in range(n-1):
  x,y=map(int, input().split())
  graph[x].append(y)
  graph[y].append(x)

queue=deque()
queue.append(1)

while queue:
  temp=queue.popleft()
  for i in graph[temp]:
    if parents[temp-1]!=i:
      parents[i-1]=temp
      queue.append(i)

for i in parents[1:]:
  print(i)