[백준알고리즘] 11725번: 트리의 부모 찾기 -Python

[백준알고리즘] 11725번: 트리의 부모 찾기 -Python

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

11725번: 트리의 부모 찾기

트리의 연결 정보가 주어졌을 때 각 노드의 부모를 모두 출력하는 문제이다.

 

처음 주어진 입력 정보를 각 노드의 번호별로 리스트를 통해서 유지했다. 그 후 head[]라는 부모 노드의 번호를 가리키는 리스트를 생성해주었고, 1번 노드부터 BFS 방식으로 문제를 풀었다.

 

각 노드와 연결된 노드 중에서 아직 head[]에 부모 노드가 결정되지 않은 노드는 현재 노드를 부모로 하도록 해주었다. 사이클이 없는 트리에 부모는 하나뿐이고 BFS로 탐색하기 때문에 부모 노드가 결정되었는지는 확인하지 않아도 될 것 같지만, 현재 노드를 루트로 하는 서브 트리로 봤을 때, 아래의 노드들의 연결 정보에는 현재 루트인 부모 노드도 연결 정보에 포함되어있기 때문에 이 부분을 없애주기 위해서 사용했다. 노드의 번호를 비교해줘도 되겠지만..

 

import sys
from collections import deque

n = int(sys.stdin.readline())

head = [0] * (n+1)
head[1] = 1

tree = {}
for i in range(1, n+1):
    tree[i] = []

for _ in range(n-1):
    v1, v2 = map(int, sys.stdin.readline().split())
    tree[v1].append(v2)
    tree[v2].append(v1)

q = deque([1])
while q:
    node = q.popleft()
    for child in tree[node]:
        if not head[child]:
            head[child] = node
            q.append(child)

for h in head[2:]:
    print(h)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다