[Python] 백준, 1991(트리)

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

1991번: 트리 순회

어젯밤에 이진트리 알고리즘 구현 공부를 하다 자서, 감이 올라왔을 때 한 문제라도 풀어보는 게 좋을 것 같아 트리 알고리즘 중에 가장 쉬운 난이도를 골랐다. 확실히 구현 자체와 문제 풀이 간의 차이는 존재하더라. 노드 클래스와 트리 클래스를 정의해서 긴 호흡으로 끌고 가는 게 당연하다고 생각했는데, 생각보다 풀이는 단순하더라.

 

 

 

# PYTHON CODE (1)

import sys

n = int(sys.stdin.readline())
tree = {}

for _ in range(n):
    a, b, c = sys.stdin.readline().split()
    tree[a] = [b, c]

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

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

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

preorder('A')
print()
inorder('A')
print()
postorder('A')

딕셔너리 메서드와 재귀의 조화랄까. 재귀는 볼수록 새로워서 걱정이다. 무슨 의미인지 알겠고 이해까지 되는데 혼자 힘으로 구현하기는 힘든 느낌이랄까. 근데 이렇게 푸는 건 내가 기존에 생각했던 노드의 느낌이 들어가있지 않아서 맞은 사람의 풀이를 참고해 노드를 이용한 풀이를 하나 더 작성해봤다.

 

 

# PYTHON CODE (2)

import sys


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


def preorder(node):
    if node is None:
        return
    print(node.data, end='')
    preorder(tree[node.left])
    preorder(tree[node.right])


def inorder(node):
    if node is None:
        return
    inorder(tree[node.left])
    print(node.data, end='')
    inorder(tree[node.right])


def postorder(node):
    if node is None:
        return
    postorder(tree[node.left])
    postorder(tree[node.right])
    print(node.data, end='')


n = int(sys.stdin.readline())
tree = {'.': None}

for _ in range(n):
    a, b, c = sys.stdin.readline().split()
    tree[a] = Node(a, b, c)

preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])

한가지 주의할 점은 노드의 왼쪽 자식이나 오른쪽 자식이 ' . ' 일 경우 할당된 노드가 없기 때문에 node.data == ' . ' 로 조건문을 작성하면 AttributeError가 발생하기 때문에, ' . ' 에 대한 값을 딕셔너리에 미리 저장해 두었다. 위에 작성한 코드보다는 시간적인 효율이 좋더라.