[python/파이썬] 백준 11725 트리의 부모 찾기

문제

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

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1 복사

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1 복사

4
6
1
3
1
4

예제 입력 2 복사

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 2 복사

1
1
2
3
3
4
4
5
5
6
6

 

 

[소스 코드]

 

import sys
sys.setrecursionlimit(10**9) #재귀의 깊이를 늘려줌(기본은 1000)

n = int(input()) # 노드의 개수

tree = [[] for _ in range(n+1)]  # 빈 트리

for _ in range(n-1): 
    a,b = map(int, sys.stdin.readline().split()) #연결된 두 개의 노드를 입력받음
    tree[a].append(b) # a 노드에 연결된 노드로 b 노드를 추가
    tree[b].append(a) # b 노드에 연결된 노드로 a 노드를 추가

parents = [0 for _ in range(n+1)] # 부모 노드 저장

def dfs(start, tree, parents): #재귀를 이용한 방법
    for i in tree[start]: # start번째 노드에 연결된 모든 노드를 탐색하는 for문
        if parents[i] == 0: # 이 노드에 방문한 적이 없다면
            parents[i] = start # 부모 노드를 저장
            dfs(i,tree,parents) # 노드 i를 시작점으로 해서 다시 탐색
     


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