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

문제 주소

백준 17725번 트리의 부모 찾기

11725번: 트리의 부모 찾기

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

www.acmicpc.net

알고리즘

트리

힌트

주어진 입력대로 노드들을 양방향으로 연결하고 1을 루트로 트리를 재구성한다.

문제풀이

1에서 출발하여 BFS로 각 노드의 부모를 찾는다.

n = int(input())
tree = [[] for i in range(n+1)]

for i in range(n-1):
    a,b=list(map(int,input().split()))
    tree[a].append(b)
    tree[b].append(a)

q = [1]
ans= {}
check = [False for i in range(n+1)]

while len(q)>0 :
    parent=q.pop(0)
    for i in tree[parent]:
        if not check[i]:
            ans[i] = parent
            q.append(i)
            check[i]=True
    #print(q)

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