[BOJ]11725 - 트리의 부모 찾기 (Python)

문제 

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

코드 

from collections import deque
import sys
input = lambda : sys.stdin.readline().strip()

def bfs():
    queue = deque()
    queue.append(1)
    while queue:
        node = queue.popleft()
        for i in graph[node]:
            if parent[i] == 0:
                parent[i] = node
                queue.append(i)


N = int(input())
graph = [[] for _ in range(N+1)]
parent = [0 for _ in range(N+1)]

for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

bfs()
for item in parent[2:]:
    print(item)

 

풀이 

트리를 탐색하는 문제이기 때문에 DFS 또는 BFS를 사용하면 쉽게 풀 수 있다 

1부터 그래프를 돌면서 1의 자식인 node를 그 다음으로 돌고 이후 자식들을 탐색한다