11725: 트리의 부모 찾기

• dfs와 bfs 두 가지 방법 모두로 구현이 가능함

import sys
from collections import deque

def dfs(start):
	for element in adjacent[start]:
		if visit[element] == 0:
			visit[element] = start # 자식 노드의 위치에 부모 노드를 저장
			dfs(element)

def bfs():
	queue = deque([])
	queue.append(1)

	while queue:
		element = queue.popleft()
		for next_element in adjacent[element]:
			if visit[next_element] == 0:
				visit[next_element] = element
				queue.append(next_element)

N = int(input())
adjacent = [[] for _ in range(N+1)]
for _ in range(N-1):
	tmp = list(map(int, sys.stdin.readline()[:-1].split(' ')))
	adjacent[tmp[0]].append(tmp[1])
	adjacent[tmp[1]].append(tmp[0])

visit = [0] * (N+1)
# dfs(1)
bfs()

for i in range(2, N+1):
	print(visit[i])

• visit 리스트를 이용하여 자식 노드의 위치에 부모 노드를 저장함