[CodingTest] BOJ1991 트리순회 ( tree ) With 파이썬

1991번: 트리 순회

 

 

◎ 문제풀이

 

순회를 하려면 '노드'를 '기억'해야 한다. '기억'을 담당하는 자료구조는 STACK이다. 나는 두 가지를 놓쳐서 이 문제를 어렵게 풀었다. 

 

1) 파이썬의 딕셔너리 자료형을 몰랐다.

 

tree = {}

딕셔너리 자료형은 Map처럼 key-value 구조로 이루어져 있다. 딕셔너리 자료형을 몰라서 인덱스로 접근하는 리스트 자료형을 사용하였다.

 

2) 재귀호출을 발상하지 못했다.

 

재귀호출은 함수의 호출을 이용한다. 함수는 STACK영역에 쌓이므로 굳이 STACK 자료구조를 만들지 않아도 재귀호출로 STACK 기능을 구현할 수 있다.

 

 

◎ 코드

 

재귀호출 + 딕셔너리 자료형을 사용하지 않은 코드

import sys
input = sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n)]

def char_num(char) :
  return ord(char) - ord("A")

def num_char(num) :
  return chr(num + ord("A"))

for i in range(n) :
  parent,left,right = map(char_num, input().split())
  graph[parent] = [left,right]


def traversal(graph,type) :
  stack = [0]
  visited = [False] * 26
  while stack :
    value = stack.pop()
    if visited[value] : print(num_char(value),end="")
    else : 
      visited[value] = True
      sub = []
      if type == "preorder" : sub = [ graph[value][1],graph[value][0],value ]
      elif type == "inorder" : sub = [ graph[value][1],value,graph[value][0] ]
      else : sub = [ value, graph[value][1],graph[value][0] ]

      for i in sub :
        if i != char_num(".") : stack.append(i)

      
traversal(graph,"preorder")
print()
traversal(graph,"inorder")
print()
traversal(graph,"postorder")

 

딕셔너리 자료형을 사용하지 않아 문자를 정수로 변환하여 문제를 풀었다. 그리고 순회를 Stack으로 구현하였다.

 

 

재귀호출 + 딕셔너리 자료형을 사용한 코드

n = int(input())
tree = {}

for _ in range(n) :
  parent, left, right = input().split()
  tree[parent] = [left,right]

def preorder(parent) :
  if parent != "." :
    print(parent,end="")
    preorder(tree[parent][0])
    preorder(tree[parent][1])

def inorder(parent) :
  if parent != "." :
    inorder(tree[parent][0])
    print(parent,end="")
    inorder(tree[parent][1])

def postorder(parent) :
  if parent != "." :
    postorder(tree[parent][0])
    postorder(tree[parent][1])
    print(parent,end="")


preorder("A")
print()
inorder("A")
print()
postorder("A")