[Python]트리 백준 11725

   문제

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

트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 여러 노드가 한 노드를 

가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나

뿐인 그래프를 트리라고 부른다.

트리에서 최상위 노드를 루트 노드(root node 뿌리 노드[*])라고 한다. 또한 노드 A가 노드

 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한

다.

 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드[*])라고 한다. 잎 노드가 아닌 

노드를 내부 노드(internal node)라고 한다.

트리에 대한 정의부터 알아봤다.

이제 문제로 들어가보자

DFS로 구현해 봐야겠다.

재귀 함수의 최대깊이를 늘려주지 않으면 런타임 에러가 발생했다.

기본적으로 1000레벨까지로 정해져 있다고 한다.

sys.setrecursionlimit(10 ** 9) 을 통해 재귀의 깊이를 늘려주었다.

import sys
sys.setrecursionlimit(10 ** 9)
 
N=int(sys.stdin.readline())#노드의 갯수
tree=[[] for _ in range(N+1)]
for _ in range(N-1):
    s,e=map(int,sys.stdin.readline().split())
    tree[s].append(e)
    tree[e].append(s)
 
 
#부모저장
parents=[0 for _ in range(N+1)]
 
 
def DFS(start,tree,parents):
    for i in tree[start]:#연결된 노드 모두탐색
        if parents[i]==0:#한번도 방문한적이 없다면
           parents[i]=start#부모노드 저장
           DFS(i,tree,parents)
 
 
DFS(1,tree,parents)
 
for i in range(2,N+1):
    print(parents[i])