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

문제

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

분석

트리의 루트를 1이라고 정했을 때, 1을 제외한 각 노드의 부모를 구하는 문제이다.

parent 배열을 생성하고 DFS를 1부터 진행하여 탐색하려는 곳과 현재 노드의 관계를 고려해 parent 배열을 채워나간다.
현재 있던 노드가 부모, 탐색하려는 노드가 자식이기 때문에 parent배열의 인덱스에는 자식노드를, 값에는 부모노드를 기입한다.

n이 100000이므로 재귀 최대 깊이를 10^5+1로 늘려준다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+1)

n = int(input())
parent = [0]*(n+1)
tree = [[] for _ in range(n+1)]
visited = [False]*(n+1)
for _ in range(n-1):
    s, e = map(int, input().split())
    tree[s].append(e)
    tree[e].append(s)

def dfs(x):
    visited[x] = True
    for nx in tree[x]:
        if not visited[nx]:
            parent[nx] = x
            dfs(nx)

dfs(1)

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

끝으로..

약간의 휴식기를 가졌고 다시 TIL을 꾸준히 작성하려 한다.
매일 하나씩 습득한 것을 정리하면 추후에 큰 자산이 될 것이다.