[백준] 11725번 : 트리의 부모 찾기(Python)

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

전체코드(Python)

# 정점의 개수를 입력 받는다.
def bfs(tree,num,start):
    # 부모가 있는 애들을 담을 공간
    box = []
    box.append(start)
    # box에 담긴 모든 숫자가 없어질때까지 순회한다.
    while len(box)!=0:
        start = box.pop(0)
        while len(tree[start-1]) != 0 :
            # 자식이 될 후보를 찾는다.
            next = tree[start-1].pop(0)
            # 만일 next의 부모가 정해지지 않았다면 next의 부모에 start를 저장한다.
            if num[next-1] == 0:
                num[next-1] = start
                # 부모가 될 후보를 넣는다.
                box.append(next)
                
    return num
# 정점의 개수를 입력받는다.
n = int(input())
# 각 정점이 들어갈 공간을 만들어둔다.
tree = [ []*n for _ in range(n) ] 
# 부모를 저장할 공간을 만들어 둔다.
parent = [0 for _ in range(n)]
# 정점 -1개까지 반복하며 점과 점사이를 연결한다.
for i in range(n-1):
    a,b = map(int,input().split())
    tree[b-1].append(a)
    tree[a-1].append(b)
# 1부터 시작해서 점의 부모를 parent에 저장한다.
parent = bfs(tree,parent,1)
# 2부터 n까지 부모를 출력한다.
for i in range(1,n):
    print(parent[i])

혹시라도 정정할 내용이나 추가적으로 필요하신 정보가 있다면 댓글 남겨주시면 감사하겠습니다.
오늘도 Jindory 블로그에 방문해주셔서 감사합니다.

 

[ 참조 ]

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