[BOJ] 백준 11725번 트리의 부모 찾기 (Python)

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 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

풀이

DFS

import sys

# recursion error 떠서 recursion limit 늘려줌
sys.setrecursionlimit(10 ** 9)

def DFS(start):
    for i in Tree[start]:
        if Parent[i] == 0:
            Parent[i] = start
            DFS(i)

n = int(sys.stdin.readline())

Tree = list(list() for _ in range(n+1))
Parent = list(0 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)

Parent[1] = -1
DFS(1)

for x in Parent[2:]:
    print(x)

처음에 DFS를 이용해 풀었지만 Recursion Error로 인해 실행이 중단되었다. 따라서 sys.setrecursionlimit(10 ** 9) 코드를 통해 recursion limit를 늘려준다.

하지만 이러한 에러를 피하기 위해서 DFS 대신 BFS도 사용해 보았다.

BFS

import sys
from collections import deque

n = int(sys.stdin.readline())
Tree = list(list() for _ in range(n+1))
Parent = list(0 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)

queue = deque([1])

while queue:
    tmp = queue.popleft()
    for i in Tree[tmp]:
        if Parent[i] == 0:
            Parent[i] = tmp
            queue.append(i)


for x in Parent[2:]:
    print(x)

결과

위가 BFS, 아래가 DFS를 사용한 결과다. DFS는 Recursion Error가 뜨긴 했지만, Recursion limit를 늘리게 된다면 BFS보다 빨리 결과가 나온다.