새로운 블로그로 이전 작업을 진행하고 있어 포스트가 새로 작성되고 있지 않습니다.

빠른 시일 내에 새로운 블로그로 인사드리겠습니다.

새로운 블로그 : https://unho.vercel.app/

본문 바로가기
알고리즘 문제풀이/Python

[백준] 9934 완전 이진 트리

by 언호 2021. 12. 17.

문제


풀이 과정

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번: 완전 이진 트리

상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래

www.acmicpc.net

 

 

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

댓글