[BOJ] 1991 : 트리 순회 [](Python)

문제 링크

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

1991번: 트리 순회

소스 코드

import sys
sys.setrecursionlimit(10**6)

def main():
    n = int(input())
    tree = {}

    for _ in range(n):
        root, left, right = input().split()
        tree[root] = (left,right)
    
    pre_answer, in_answer, post_answer = [], [], []

    pre_order(tree, 'A', pre_answer)
    in_order(tree, 'A', in_answer)
    post_order(tree, 'A', post_answer)

    print(''.join(pre_answer))
    print(''.join(in_answer))
    print(''.join(post_answer))

def pre_order(tree, root, pre_answer):
    if root != '.':
        pre_answer.append(root)
        pre_order(tree, tree[root][0], pre_answer)
        pre_order(tree, tree[root][1], pre_answer)

def in_order(tree, root, in_answer):
    if root != '.':
        in_order(tree, tree[root][0], in_answer)
        in_answer.append(root)
        in_order(tree, tree[root][1], in_answer)

def post_order(tree, root, post_answer):
    if root != '.':
        post_order(tree, tree[root][0], post_answer)
        post_order(tree, tree[root][1], post_answer)
        post_answer += root

if __name__ == '__main__':
    main()

 

해설

• 트리, 재귀

이진 트리는 루트 노드를 중심으로 자식 노드 두 개를 좌우로 갖는 형태의 자료구조입니다.

따라서 이전에 살펴보던 그래프 구조와 다르게 딕셔너리를 구성하면 됩니다.

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

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

 

다음으로는 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)입니다.

저도 이 개념이 처음이어서 자료를 찾아봤는데요, 이 내용을 먼저 정리해보겠습니다.예시를 통해 알아보죠.

     1
    / \
   2   3
  / \
 4   5

결과적으로 말하면 각 순회의 결과는 다음과 같습니다.

• preorder : 1 - 2 - 4 - 5 - 3
• inorder : 4 - 2 - 5 - 1 - 3
• postorder : 4 - 5 - 2 - 3 - 1

preorder는 무조건 '루트 노드의 왼쪽부터 탐색'하는 방식을 말합니다.

inorder는 '왼쪽 노드로부터 거꾸로 타고 올라오며 오른쪽으로 뻗어나가며 탐색'하는 방식을 말합니다.

postorder는 '가장 바닥의 같은 계층의 노드로부터 오른쪽으로 뻗어나가며 탐색'하는 방식을 말합니다.

 

그래서 재귀 방식으로 코드를 작성할 때도 이 내용을 간단하게 반영할 수 있습니다.

def pre_order(tree, root, pre_answer):
    if root != '.':
        pre_answer.append(root)
        pre_order(tree, tree[root][0], pre_answer)
        pre_order(tree, tree[root][1], pre_answer)

def in_order(tree, root, in_answer):
    if root != '.':
        in_order(tree, tree[root][0], in_answer)
        in_answer.append(root)
        in_order(tree, tree[root][1], in_answer)

def post_order(tree, root, post_answer):
    if root != '.':
        post_order(tree, tree[root][0], post_answer)
        post_order(tree, tree[root][1], post_answer)
        post_answer += root

순서를 보시면 해당 루트를 정답에 추가하는 위치가 왼쪽, 중간, 마지막임을 알 수 있습니다.

사실 이런 식으로 코드를 작성하기 때문에 이름이 각각 pre/in/post order로 붙었겠죠?

 

 

참고로 굳이 이렇게 main 함수와 구분지으며 함수를 추가하고 argument를 여러 개 받을 필요는 없습니다.

다른 분들의 풀이를 봐도 answer 리스트에 root를 추가하는 방식이 아니라 출력으로 정답 판정을 받을 수 있습니다.

하지만 그런 풀이는 프로그래머스 환경에서 애를 먹게 됩니다.

특히 재귀 관련해서는 내가 생각한 로직은 맞더라도 실제 정답으로 추가되지 않는 경우가 있기 때문에,

코딩테스트를 준비하시는 분들이라면 이 내용을 참고하셔서 정답 문자열을 만드는 방식을 고민해보시기 바랍니다.