[백준] 11725 - 트리의 부모 찾기 (BFS)

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

11725번: 트리의 부모 찾기

from collections import deque
 
n = int(input())
arr = [list() for _ in range(n + 1)]
answer = [-1] * (n + 1)
for _ in range(n - 1):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)
 
q = deque()
q.append(1)
 
while q:
    now = q.popleft()
    for node in arr[now]:
        if answer[now] != node:
            answer[node] = now
            q.append(node)
 
for ans in answer[2:]:
    print(ans)

BFS로 풀면 된다.

1이 루트 노드라고 했으니, 1부터 시작하여 각 노드에 연결된 노드를 탐색하며 부모 노드를 초기화하면 된다.