접근방법

• 입력값을 가지고 트리를 인접배열로 구현한다.
• 루트를 1로주고 순회하면서 각노드의 부모를 저장한다
  -> 부모를 저장하는 자료구조가 하나 더필요하겠다

코드

import sys
sys.setrecursionlimit(10**9)

n = int(input())

tree = [[] for _ in range(n+1)]
visit = [0] * (n+1)

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

parent = [0] * (n+1)

def dfs(tree, v, visit):
    visit[v] += 1
    for i in tree[v]:
        if visit[i]==0:
            parent[i] = v
            dfs(tree,i,visit)

dfs(tree,1,visit)

for idx,i in enumerate(parent):
    if idx > 1:
        print(i)

    

챙겨갈점

• dfs ,bfs 개념
• sys.setrecursionlimit(10**9) 파이썬은 재귀의 깊이 제한이 굉장히 낮으므로 올려준다.
• 내가 원하는 정보를 어떤자료구조에 어떻게 언제 담을지 잘 고민하자.