[PYTHON] 백준 5639 - 이진 검색 트리

성능 요약

메모리: 449416 KB, 시간: 3464 ms

분류

그래프 이론, 그래프 탐색, 재귀, 트리

문제 설명

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

---

아이디어, 문제풀이

• 전위 순회를 트리로 바꾼다.
• 만들어진 트리를 활용해 후위 쉰회의 결과를 출력한다.

---

TROUBLE SHOOTING

• 이 문제풀이에 일치하는 풀이법은 아니였겠지만, 학습을위해 입력값을 트리로 만든뒤, 그 트리를 통해 순회를 출력하는 방식으로 풀이했다. 트리 학습을 위해!
  이론도 쉽고, 직접 그려보는 것도 쉬운데, 코드 구현이 정말 헬이다. 아무것도 없는 상태로 트리를 구현한다는건… 불가능에 가깝단 생각이든다. 다른 방식으로 우회해서 풀더라도 엄청난 시간이 걸리지 않을까?

• 두가지 알고리즘을 공유할 예정인데, 첫번째로는 트리를 저장하는 방법들이다. 나는 크게 튜플, 딕셔너리 형태로 저장하는 두가지 방법을 학습하며 구현했다.

  • 튜플

    def LAB_tree_tuple(graph): 
        if not graph:
            return None
    
        root = graph[0]
    
        # 왼쪽 하위 트리와 오른쪽 하위 트리로 나눈다.
        left_subtree = [x for x in graph if x < root]
        right_subtree = [x for x in graph if x > root]
    
        left = LAB_tree_tuple(left_subtree)
        right = LAB_tree_tuple(right_subtree)
    
        return (root, left, right)

  • 딕셔너리

     def LAB_tree_diction(graph):
         if not graph:
             return None
     
         root = graph[0]
     
         # 왼쪽 하위 트리와 오른쪽 하위 트리로 나눈다.
         left_subtree = [x for x in graph if x < root]
         right_subtree = [x for x in graph if x > root]
     
         left = LAB_tree_diction(left_subtree)
         right = LAB_tree_diction(right_subtree)
     
         return {"root": root, "left": left, "right": right}

    보여지는 그대로, 리턴값에 내가 뽑아내고자 하는 형태로 출력하면 된다. 안쪽에 들어있는 알고리즘은 개념정리에서 더 깊게 다루겠다. 입력받은 전위순회 배열을 트리형태로 만들어주는 알고리즘이다. 다른 순회배열도 정리해서 개념정리에 추가해볼 예정이다.

• 두번째로, 순회 알고리즘인데, 이 코드는 백준 1991번 문제에서 사용한 알고리즘을 그대로 채용했다. 기본적인 틀을 알면 역시 활용하는 폭도 늘어나고, 이해도 더 빠르게 되는 것 같다. 문제에서 요구한 후위순회 뿐 아니라, 모든 순회의 코드를 작성해 연습했다.

  #전위순회
  def LAB(tree):
      result = []
      if tree:
          result.append(tree["root"])
          result.extend(ABL(tree["left"]))
          result.extend(ABL(tree["right"]))
      return result   
  
  #중위순회
  def ALB(tree):
      result = []
      if tree:
          result.extend(ABL(tree["left"]))
          result.append(tree["root"])
          result.extend(ABL(tree["right"]))
      return result
  
  #후위순회
  def ABL(tree):
      result = []
      if tree:
          result.extend(ABL(tree["left"]))
          result.extend(ABL(tree["right"]))
          result.append(tree["root"])
      return result

• 트리 문제는 사실 많이 접해본 적이 없어서, 새로운 개념을 익힌다는 느낌으로 접근했다. 여기서 난이도가… 더 올라간다면 캐치해 낼 수 있을까? 싶은 생각이 들긴 한다. 그래도 이 문제까지는 어렵지 않게 해결할 수 있었다.

---

코드

#https://www.acmicpc.net/problem/5639
#이진 검색 트리
#5639

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

graph = []
while True:
    try:
        a = int(input())
        graph.append(a)
    except:
        break

###########################################################

#트리를 튜플형태로 저장하는 방법
def LAB_tree_tuple(graph): 
    if not graph:
        return None

    root = graph[0]

    # 왼쪽 하위 트리와 오른쪽 하위 트리로 나눈다.
    left_subtree = [x for x in graph if x < root]
    right_subtree = [x for x in graph if x > root]

    left = LAB_tree_tuple(left_subtree)
    right = LAB_tree_tuple(right_subtree)

    return (root, left, right)

#트리를 딕셔너리 형태로 저장하는 방법
def LAB_tree_diction(graph):
    if not graph:
        return None

    root = graph[0]

    # 왼쪽 하위 트리와 오른쪽 하위 트리로 나눈다.
    left_subtree = [x for x in graph if x < root]
    right_subtree = [x for x in graph if x > root]

    left = LAB_tree_diction(left_subtree)
    right = LAB_tree_diction(right_subtree)

    return {"root": root, "left": left, "right": right}

###########################################################     

#전위순회
def LAB(tree):
    result = []
    if tree:
        result.append(tree["root"])
        result.extend(ABL(tree["left"]))
        result.extend(ABL(tree["right"]))
    return result   

#중위순회
def ALB(tree):
    result = []
    if tree:
        result.extend(ABL(tree["left"]))
        result.append(tree["root"])
        result.extend(ABL(tree["right"]))
    return result

#후위순회
def ABL(tree):
    result = []
    if tree:
        result.extend(ABL(tree["left"]))
        result.extend(ABL(tree["right"]))
        result.append(tree["root"])
    return result           

###########################################################

tree = LAB_tree_diction(graph)
result_list = ABL(tree)

for i in range(len(result_list)):
    print(result_list[i])