[백준] 11725 트리의 부모 찾기 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/11725
• 🔑 DFS
  • 양방향 그래프로 트리를 표현
  • 1번 노드부터 출발
  • 자식 노드에 도착하면 자식 노드 인덱스에 부모 노드 번호 저장 (answer 리스트)
  • DFS 끝나면 answer [2]부터 출력

 

from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

n = int(input())
tree = defaultdict(list)

for i in range(n-1):
    p, c = map(int, input().split())
    tree[p].append(c)
    tree[c].append(p)

answer = [0] * (n+1)
visit = [0] * (n+1)
visit[1] = 1

def dfs(node):   
    for c in tree[node]:
        if visit[c] == 0:
            answer[c] = node
            visit[c] = 1
            dfs(c)

dfs(1)

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