[Python][백준] 11725_트리의 부모 찾기

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

11725번: 트리의 부모 찾기

문제

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

 

입력

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

 

출력

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

---

트리의 노드별로 부모 노드의 인덱스를 찾는 문제로 어떤 방법으로 풀이해야 좋을지 조금 고민을 했는데, 간단한 그래프의 DFS(깊이우선탐색) 문제였다.

 

Root 로 주어진 1번 노드부터 DFS를 수행하면 연결관계를 가진 노드가 자식임을 알 수 있으므로, 이 정보를 parents 배열에 저장하여 문제를 풀이하였다.

 

최대 노드 갯수가 100,000이기 때문에 런타임 에러 (RecursionError)가 발생하지 않기 위해서는

sys.setrecursionlimit(10**5 + 1) 를 설정해주어야 한다.

 

import sys
sys.setrecursionlimit(10**6)

def dfs(root):
    for a in arr[root]:
        if not vi[a]:
            vi[a] = True
            dfs(a)
            parent[a] = root

### MAIN
n = int(sys.stdin.readline().strip())

arr = [[] for _ in range(n+1)]

for _ in range(n-1):
    node1, node2 = map(int, sys.stdin.readline().strip().split())
    arr[node1].append(node2)
    arr[node2].append(node1)

parent = [-1 for _ in range(n+1)]
vi = [False for _ in range(n+1)]
dfs(1)

# print(parent)
for r in range(2, len(parent)):
    print(parent[r])