[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 1991번 _ 트리 순회

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

1991번: 트리 순회

[문제]

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

 

[입력]

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

[출력]

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

 

[아이디어]

1) 전위 순회: 루트를 먼저 방문

중위 순회: 왼쪽 자식을 방문한 뒤 루트를 방문

후위 순회: 왼쪽과 오른쪽 자식을 방문한 뒤 루트를 방문

2) 재귀적 구현이 가능하다.

 

class Node():
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node
def preorder(node):
    print(node.data, end = '')
    if node.left_node !='.':
        preorder(tree[node.left_node])
    if node.right_node !='.':
        preorder(tree[node.right_node]) 
def inorder(node):
    if node.left_node !='.':
        inorder(tree[node.left_node])
    print(node.data, end = '')
    if node.right_node !='.':
        inorder(tree[node.right_node])
def postorder(node):
    if node.left_node !='.':
        postorder(tree[node.left_node])
    if node.right_node !='.':
        postorder(tree[node.right_node]) 
    print(node.data, end = '')
  
n=int(input())
tree = dict()
for i in range(n):
    a,b,c = input().split()
    tree[a] = Node(a,b,c)   
    
preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])

나동빈씨는 내게 꿈과 희망을 준다. 세 순회 방식이 순서의 차이라는 것이 중요하다.

n=int(input())
tree = dict()
ans = ['']*3
for i in range(n):
    a,b,c = input().split()
    tree[a] = [b,c]

def traversal(x):
    if x!='.':
        ans[0] += x
        traversal(tree[x][0])
        ans[1] += x
        traversal(tree[x][1])
        ans[2] += x

traversal('A')
print(*ans, sep='\n')

간단한 문제이기 때문에, 위처럼 짧은 코딩도 가능하다. 순서를 잘 활용해 구현한 재귀가 인상적이다. (이해하는데도 한참 걸렸다..) 노드가 없음을 의미하는 '.'을 만나면 자동으로 탈출도 가능하고,, 각 방법에 대해 자신과 관계 없는 부분을 지우고 생각하면 위 클래스를 활용한 방법과 동일한 코드다.