백준(11725) - 트리의 부모 찾기 Python

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

문제풀이: BFS 알고리즘, 파이썬

노드와 간선의 정보가 주어진 후에, 루트 노드를 1이라고 지정했을 때, 각 노드의 부모 노드를 구하는 문제이다.

1. 그래프로 노드들의 정보를 양방향으로 받는다.
2. 부모 노드를 0으로 초기화 시킨다.
3. deque에 부모 노드 1을 넣고, 그래프에서 하나씩 빼면서 bfs 연산을 해주면 된다.

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
graph = [[] for i in range(n+1)]
parent = [0] * (n+1)

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

q = deque()
q.append(1)

while q:
    x = q.popleft()
    for i in graph[x]:
        if parent[i] == 0:
            parent[i] = x
            q.append(i)

for child in parent[2:]:
    print(child)