백준 11725 파이썬 - 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

코드

import sys
sys.setrecursionlimit(10**9)
n = int(sys.stdin.readline())
parent = [-1] * (n + 1)
tree = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    tree[a].append(b)
    tree[b].append(a)
def dfs(s):
    for i in tree[s]:
        if parent[i] == -1:
            parent[i] = s
            dfs(i)
dfs(1)
for i in range(2, n + 1):
    print(parent[i])

풀이

dfs함수에 1부터 넣어 넣은 값이 인덱스인 tree리스트의 값에 대응되는 parent리스트의 값이 초기값인 -1이면 함수에 넣은 매개변수 값으로 교체해주고 다시 dfs를 그 tree리스트의 값으로 돌린다. 이러면 parent리스트에는 각 인덱스의 값의 부모 노드의 숫자가 저장된다.