백준 11725 - 트리의 부모 찾기 [파이썬]

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

11725번: 트리의 부모 찾기

---

풀이 과정

트리가 주어지고, 1번 노드가 루트라고 할 때 각 노드의 부모 노드 번호를 구하는 문제이다.

 

root 노드인 1번부터 시작해 BFS or DFS를 사용해서 트리를 탐색하고, 각 노드의 부모 노드를 갱신해주면 된다.

---

소스 코드

import sys
import collections

N = int(sys.stdin.readline())
graph = collections.defaultdict(list)
parent = collections.defaultdict(int)
Q = collections.deque([])
discovered = [False for _ in range(N+1)]

for _ in range(N-1):
    A, B = map(int, sys.stdin.readline().split())
    graph[A].append(B)
    graph[B].append(A)

Q.append(1)

while Q:
    cur = Q.popleft()
    for i in graph[cur]:
        if discovered[i]:
            continue
        parent[i] = cur
        discovered[i] = True
        Q.append(i)

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