11725 트리의 부모 찾기 (파이썬)

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

11725번: 트리의 부모 찾기

취업준비를 위해 본격적으로 코딩테스트 문제를 다시 풀어보았습니다. 해당 문제의 난이도는 실버2이며 분류는 트리입니다. 트리 문제의 풀이법을 알면 쉽게 풀 수 있는 문제입니다.

풀이 방식은 다음과 같습니다.

1. 그래프를 먼저 만든다.

2. 1부터 BFS를 수행합니다. 

3. 큐에 넣기 전 현재 노드의 번호를 부모로 저장합니다.

 

코드

import sys
from collections import defaultdict, deque

input = lambda: sys.stdin.readline().rstrip()

graph = defaultdict(list)
N = int(input())
parents = [0] * (N + 1)
visited = [False] * (N + 1)
q = deque()

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

q.append(1)
while q:
    now = q.popleft()
    children = graph[now]
    for c in children:
        if parents[c] == 0:
            parents[c] = now
            q.append(c)

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