[백준] 9934 완전 이진 트리

문제

---

풀이 과정

1) 문제 이해 및 접근

문제에서 '완전 이진 트리' 및 주어진 조건, 노드의 총 개수 등을 확인하였을때, '포화 이진 트리' 라고 판단하였습니다.

트리의 중위 순회의 특징인 왼쪽 "자식 노드 / 부모 노드 / 오른쪽 자식 노드" 고려하여 재귀를 이용하는 풀이 방법을 생각했습니다.

2) 알고리즘

• 트리 순회 (중위 순회, In_order)
• 재귀

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

# 중위 순회를 하며 각 노드를 층별로 배치 시키는 함수
def solution(left, root, right, depth):                     # 왼쪽 자식 노드 시작 인덱스 / 부모 노드 인덱스
                                                            # 오른쪽 자식 노드 끝 인덱스 / 트리의 레벨
    if left >= root:                                        # 리프 노드일때
        level[depth].append(in_order_li[root])              # 현재 노드의 레벨에 노드 번호 추가
        return

    solution(left, (left+root)//2, root-1, depth+1)         # 왼쪽 자식 노드 재귀 호출
    level[depth].append(in_order_li[root])                  # 부모 노드 해당하는 층에 노드 번호 추가
    solution(root+1, (root+right+1)//2, right, depth+1)     # 오른쪽 자식 노드 재귀 호출


K = int(sys.stdin.readline())                               # 트리의 레벨(깊이)
in_order_li = list(map(int, sys.stdin.readline().split()))  # 문제에서 주어진 중위순회 한 결과값
level = [[] for _ in range(K)]                              # 트리의 각 레벨별 노드 리스트

solution(0, (2**K-1)//2, 2**K-1, 0)                         # 트리 중위 순회시키는 함수 호출

for i in range(K):          # 출력
    print(*level[i])

---

결과 및 학습한 내용

1) 어려웠던 내용

재귀 호출을 하는 과정에서 노드들의 인덱스를 컨트롤 하는 부분에 주의를 기울였습니다.

---

문제 링크

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

9934번: 완전 이진 트리

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다