[백준] 11725번: 트리의 부모 찾기 - python

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

11725번: 트리의 부모 찾기

 

아이디어

 

인접행렬로 값을 저장 후 dq를 생성한 뒤 루트트리 1을 집어넣고 BFS로 진행한다. 그 후 펼쳐나가면서 answer에 pop한 now를 집어넣으면서 전체를 탐험.

from collections import deque
n = int(input())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)
answer = [0] * (n+1)
for i in range(n-1):
    a, b =  map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

print(graph)

dq = deque([1])
while dq:
    now = dq.popleft()
    for i in graph[now]:
        if visited[i] == 0:
            answer[i] = now
            visited[i] = 1
            dq.append(i)

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