[Python] 백준 1991번 트리 순회 / 재귀함수와 딕셔너리 이용하기

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

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

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

가 된다.

입력

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

예제 입력 1

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

예제 출력 1 

ABDCEFG
DBAECFG
DBEGFCA

 

 

 

아이디어 생각하기

 

이 문제를 딱 봤을 때 1학년 자료구조 때 배운 전위순회, 중위순회, 후위순회가 떠올랐지만... 기억이 안 나서 전위 중위 후위를 다시 공부해야하나 생각했다... 하지만 풀이를 찾아보니 위 개념을 몰라도 풀 수 있다!

문제에서 

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

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

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

명시하고 있으므로, 

전위 순회: 1. 루트출력 2. 재귀로 왼쪽 자식 탐색 2. 재귀로 오른쪽 노드 탐색

중위 순회: 1. 재귀로 왼쪽 탐색 2. 루트출력 3.재귀로 오른쪽 노드 탐색

후위 순회 : 1. 재귀로 왼쪽 탐색 2. 오른쪽 노드탐색 3. 루트 출력

함수를 각각 구현하고, 시작 노드는 무조건 'A'이므로,  함수 실행 시 'A'를 인자로 넣어주면 된다.

 

그렇다면 트리는 어떻게 만들어야할까? 

이게 진짜 문제였다... 이중배열로 그래프를 만들어야하나 고민했는데, 딕셔너리를 이용해

각 루트를 key값으로 하고, 자식 노드를 value로 넣어주면 된다.

{'A': ('B', 'C'), 'B': ('D', '.'), 'C': ('E', 'F'), 'E': ('.', '.'), 'F': ('.', 'G'), 'D': ('.', '.'), 'G': ('.', '.')}

 

 

 

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**8)  # 재귀함수 리미트하여 메모리 초과 방지

n = int(input())
# 딕셔너리로 트리 구현
tree = {}
for i in range(n):
    root, left, right = map(str, input().split())  # 루트, 왼쪽자식, 오른쪽 자식
    tree[root] = left, right  # {'A': ('B', 'C')}


def preorder(v):  # 전위순회
    if v != ".":  # 루트 노트가 .이 아니면 (자식이 있다면)
        print(v, end="")
        preorder(tree[v][0])  # 재귀적으로 왼쪽 노드 탐색
        preorder(tree[v][1])  # 재귀적으로 오른쪽 노드 탐색


def inorder(v):  # 중위순회
    if v != ".":  # .이 아니면
        inorder(tree[v][0])  # 재귀적으로 왼쪽 노드 탐색
        print(v, end="")  # 루트 출력
        inorder(tree[v][1])  # 재귀적으로 오른쪽 노드 탐색


def postorder(v):  # 후위순회
    if v != ".":  # .이 아니면
        postorder(tree[v][0])  # 재귀적으로 왼쪽 노드 탐색
        postorder(tree[v][1])  # 재귀적으로 오른쪽 노드 탐색
        print(v, end="")  # 루트 출력

#루트노드 'A'
preorder('A')
print("")
inorder('A')
print("")
postorder('A')