[백준] 9934 : 완전 이진 트리 (파이썬)

트리, 재귀 문제

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

---

접근 방식

3
1 6 4 3 5 2 7

 

주어진 입력과 그래프의 형태를 비교해보면, 그래프를 중위 순회한 결과가 입력 배열로 주어졌다는 사실을 알 수 있다.

따라서, 중위 순회 결과를 기반으로 트리를 재구성한 후, 각 깊이에 위치한 노드들을 출력해주면 된다.

---

💡 풀이코드 (성공)

import sys 
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

graph = [[] for _ in range(n)]
depth = 0

def recursive(start, end, depth):
    if start >= end : return 

    mid = (start + end) // 2

    recursive(start, mid, depth + 1)
    graph[depth].append(arr[mid])
    recursive(mid + 1, end, depth + 1)

recursive(0, 2 ** n - 1, depth)
for i in graph:
    print(*i)

 

트리 순회

이진 트리를 중위 순회(in-order traversal)한 결과에서 트리를 재구성하고, 각 깊이에 있는 노드들을 출력해주었다.

트리의 깊이

현재 트리의 깊이에 해당하는 노드를 graph[depth] 리스트에 추가해준다.

이때, 트리의 깊이는 재귀 호출된 깊이를 활용하여 쉽게 알 수 있다. 

 

트리의 깊이에 해당하는 노드를 graph에 추가해주는 코드를 1), 2), 3) 어느 위치에 두든 상관없다. 

그 이유는 이 문제에서 트리 순회한 결과를 출력하는 것이 아닌, 트리의 해당 깊이(depth)에 위치하는 노드들을 순서대로 출력하는 것이 목적이기 때문이다.

recursive(start, mid, depth + 1) # 1) 
graph[depth].append(arr[mid]) # 2) 
recursive(mid + 1, end, depth + 1) # 3)