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

문제

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

코드

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

n = int(input())

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

for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
    
def dfs(start):
    for i in tree[start]:
        if parents[i] == 0:
            parents[i] = start
            dfs(i)
            
dfs(1)

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

설명

우선 dfs 제한을 풀어주고 시작한다.

입력값을 받아주고,
노드의 연결 관계를 세팅할 tree와
각 노드의 부모 정보를 담을 parents를 만들어준다.

이후 n-1회만큼 반복하며 연결 관계를 세팅해 준다.

dfs는 시작점에 대한 정보를 가지고 돌린다.
시작하는 노드의 연결관계에 있는 노드들에 대해서(1번 문제의 1의 경우 4와 6)
만약 그 노드들의 부모가 0으로 되어있다면(부모가 세팅되지 않았다면)
시작점을 부모로 만들어주고 해당 노드에 대해서 추가로 dfs를 돌린다.

트리의 루트를 1로 가정했기 때문에 루트 노드를 1로 하고 dfs를 돌려준다.
따라서 dfs(1)을 해준다.

이후 parents의 내용을 2번부터 출력해 준다.