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

import sys
from collections import deque

n = int(sys.stdin.readline())

graph = [[] for _ in range(n + 1)]  # 각 노드에 연결된 다른 노드 번호들 저장하는 리스트 (0번 노드는 사용 X)
parent = [0]*(n+1)   # 각 노드를 인덱스로 생각하고 그 자리에 부모 노드 저장

for _ in range(n - 1):   # 간선의 개수 (노드개수 n - 1)
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)  # 무방향 = 양방향

def bfs(node):
    queue = deque([node])  # 큐 초기화 + 시작 노드 추가
    while queue:
        node = queue.popleft()   # 큐에서 노드 꺼내기
        for n in graph[node]:   # 현재 노드에 연결된 모든 노드를 순회하기 위함
            if parent[n] == 0:  # 부모 노드가 설정되지 않은 경우
                parent[n] = node   # 부모 노드를 설정
                queue.append(n)   # 다음에 탐색할 노드로 지정하기 위함

bfs(1)

for i in parent[2:]:   # 2번 노드의 부모부터 출력 시작
    print(i)

'BFS + 양방향 트리' 기본 문제 (반복되는 패턴의 유형이므로 흐름 이해하고 잊지 말기)