[BOJ] 11725 | 트리의 부모 찾기

문제링크

---

11725 | 트리의 부모 찾기

풀이과정

---

Softeer | 거리 합 구하기 문제를 풀다가 내가 트리를 이해를 잘 못하나 .. 라는 생각으로 백준 트리섹션으로 돌아왔다 .. 하아

이 문제는 단순히 트리에서 bfs를 하면 되는 문제였다.

1번이 무조건 루트노드라서 1의 자식인 정점을 찾고 다시 이 노드들의 자식인 정점을 찾아주면 부모-자식 관계를 파악할 수 있다.

코드

---

import sys
from collections import deque

N = int(input())
trees = [[0] for _ in range(N+1)]
parents = [0] * (N+1)

for _ in range(N-1):
    a, b = map(int, sys.stdin.readline().split())
    trees[a].append(b)
    trees[b].append(a)

parents[1] = 0

q = deque()
q.append(1)

while q:
    node = q.popleft()
    for next in trees[node]:
        if parents[next] == 0:
            parents[next] = node
            q.append(next)

for i in range(2, N+1):
    print(parents[i])

결과

---