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

문제출처]

 

---

문제요약

트리의 부모 찾기 (find parent) 문제

풀이

파이썬 딕셔너리를 이용한 그래프 구현 <참조>https://zero-rabbit.tistory.com/47

[백준] 11724 연결 요소의 개수

---

find parent

def find_parent(start):
    for i in tree[start]:
        if parents[i] == 0:
            parents[i] = start
            find_parent(i)

 

---

소스코드는 Python 3으로 작성되었습니다.

import sys

# recursion 제한을 늘려줘야된다
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

n = int(input())
tree = {i: [] for i in range(1, n + 1)}
parents = [0 for _ in range(n + 1)]
for _ in range(n - 1):
    node1, node2 = map(int, input().split())
    tree[node1].append(node2)
    tree[node2].append(node1)


def find_parent(start):
    for i in tree[start]:
        if parents[i] == 0:
            parents[i] = start
            find_parent(i)


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