[백준] 1991번-(Python 파이썬) - Tree

Choe Dong Ho·2021년 7월 5일
0

백준(python)

목록 보기
41/47

문제링크 : https://www.acmicpc.net/problem/1991

트리문제는 처음 풀어봐서 공부를 더 해야겠다는 생각이 들었다. 처음엔 전위,중위,후위 순회가
어떤 건지 몰라 다른 분들의 코드를 보고 풀어보면서 이해하였다.

간단하게 생각하면
전위 순회 : 뿌리 -> 왼쪽 자식 -> 오른쪽 자식
중위 순회 : 왼쪽 자식 -> 뿌리 -> 오른쪽 자식
후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 뿌리
이렇게 순회 하면 되고 결국은 구현을 해두고 재귀를 돌때 출력을 언제 하나의 차이였었다.

구현을 못해 결국 다른 분들의 코드를 보고 공부하였지만 이걸 기회로 다른 문제들에서도 자연스럽게 응용할 수 있게 더 노력해야겠다.

내가 처음 보고 공부한 분의 코드

import sys

input = sys.stdin.readline

n = int(input())
s = [[0] * 3 for _ in range(26)]

def preorder(a):
    print(a, end="")
    if s[ord(a)-65][1] != ".":
        preorder(s[ord(a) - 65][1])
    if s[ord(a)-65][2] != ".":
        preorder(s[ord(a) - 65][2])

def inorder(a):
    if s[ord(a)-65][1] != ".":
        inorder(s[ord(a) - 65][1])
    print(a, end="")
    if s[ord(a)-65][2] != ".":
        inorder(s[ord(a) - 65][2]) 

def postorder(a):
    if s[ord(a)-65][1] != ".":
        postorder(s[ord(a) - 65][1])
    if s[ord(a)-65][2] != ".":
        postorder(s[ord(a) - 65][2])
    print(a, end="")

for i in range(n):
    node, left, right = map(str, input().split())
    item = ord(node) - 65
    s[item][0], s[item][1], s[item][2] = node, left, right

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

이건 클래스를 이용하여 직관적으로 더 보기 쉽게 풀어내신 분의 코드이다.
두번째로 보고 공부한 분의 코드

import sys
input = sys.stdin.readline

class Node:
  def __init__(self, item, left, right):
    self.item = item
    self.left = left
    self.right = right

def preorder(node):
  print(node.item, end="")
  if node.left != '.':
    preorder(tree[node.left])
  if node.right != '.':
    preorder(tree[node.right])

def inorder(node):
  if node.left != '.':
    inorder(tree[node.left])
  print(node.item, end="")
  if node.right != '.':
    inorder(tree[node.right])

def postorder(node):
  if node.left != '.':
    postorder(tree[node.left])
  if node.right != '.':
    postorder(tree[node.right])
  print(node.item, end="")

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

for _ in range(n):
  node, left, right = map(str, input().split())
  tree[node] = Node(item=node, left=left, right=right)

preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])
profile
i'm studying Algorithm

0개의 댓글