[백준] 11725번 - 트리의 부모 찾기

---

문제 분석

트리를 어떻게 구조화 할지에 대한 문제이다.
인접리스트로 트리의 구조를 만들어보고, DFS를 통해 비교해가면서, 부모노드의 번호를 저장해주면 된다.
이때 트리의 루트 노드가 1이라고 주어져 있으므로, 1번 부터 DFS를 진행하면 된다.

---

소스 코드

# 트리의 부모 찾기

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())
arr = [[] for _ in range(N + 1)]
result = [0] * (N + 1)
visited = [False] * (N + 1)

for _ in range(N - 1):
    f, s = map(int, input().split())
    arr[f].append(s)
    arr[s].append(f)


def DFS(idx, p):
    visited[idx] = True
    result[idx] = p

    for v in arr[idx]:
        if not visited[v]:
            DFS(v, idx)


DFS(1, 1)

for v in result[2: N + 1]:
    print(v)