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

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

11725번: 트리의 부모 찾기

 

문제 풀기

• 트리의 부모를 찾는 문제. 너비 탐색인 bfs를 사용하는 것이 맞다고 생각하고 풀이했다
• parent[1]은 0만 아니게 초기화 해주면 된다

# 부모에 있는 자식들을 구하는 것은 bfs

from collections import deque
n = int(input())
graph = [[] for _ in range(n+1)]
parent = [0] * (n+1)
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

queue = deque([1])
parent[1] = -1
while queue:
    v = queue.popleft()
    # print(graph[v])
    for i in graph[v]:
        if parent[i] == 0:
            queue.append(i)
            parent[i] = v 

# print(parent[2:])
for i in parent[2:]:
    print(i)