[알고리즘][Python] 백준 11725 트리의 부모 찾기 문제 풀이

문제 출처 : www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

---

문제 해석 : 1번을 루트로 하는 트리가 있다. 이때 순서에 상관없이 노드의 연결 관계가 주어질 때 각 노드의 부모를 구하여 출력하라

 

문제 풀이 : 모든 트리를 입력 받으면서 트리를 구성하고 1번 루트 부터 차례로 밑으로 내려가면서 부모를 체크해 주면 된다. 

---

풀이 코드

import sys
input = sys.stdin.readline

N = int(input())
parent = [0] * (N+1)
visited = [0] * (N+1)
tree = {}

for _ in range(N-1):
    x, y = map(int, input().split())

    if x in tree.keys():
        tree[x].append(y)
    else:
        tree[x] = [y]

    if y in tree.keys():
        tree[y].append(x)
    else:
        tree[y] = [x]
Q = []
for element in tree[1]:
    Q.append([element, 1])

while Q:
    node, par = Q.pop(0)

    parent[node] = par
    visited[node] = 1

    for element in tree[node]:
        if visited[element] == 0:
            Q.append([element, node])

for i in range(2, len(parent)):
    print(parent[i])

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.