그래프를 통해 트리를 만들고, 부모를 저장하기 위한 리스트를 만들었다
bfs를 사용해 트리를 방문하면서 부모의 값을 갱신해주었다
dfs보다 메모리를 적게 사용했지만, 시간은 조금 더 느렸다...(?)
소스 코드
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
parent = [0] * (n+1)
graph = [[] for _ in range(n+1)]
# 트리 생성
for _ in range(n-1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
q = deque([1])
while q:
now = q.popleft()
for i in graph[now]:
if parent[i] == 0:
parent[i] = now
q.append(i)
for i in range(2, n+1):
print(parent[i])
재귀 최대깊이 지정을 위해 setrecursionlimit 사용
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
parent = [0] * (n + 1)
def dfs(s, graph, parent):
for i in graph[s]:
if parent[i] == 0:
parent[i] = s
dfs(i, graph, parent)
dfs(1, graph, parent)
for i in range(2, n + 1):
print(parent[i])