백준 문제 풀이 - 트리 순회 1991번

📜 문제 이해하기

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

💡 문제 재정의

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

✏️ 계획 수립

재귀를 활용하면 쉽게 풀 수 있는 문제이다.
각 행을 이차원 배열로 저장해서 순회할때마다 그에 해당하는 배열을 재귀호출하면 문제가 풀린다.

💻 계획 수행

def pre_order(node, _tree):
    print(node[0], end='')
    if node[1] != '.':
        for info in tree:
            if info[0] == node[1]:
                pre_order(info, _tree)
    if node[2] != '.':
        for info in tree:
            if info[0] == node[2]:
                pre_order(info, _tree)


def in_order(node, _tree):
    if node[1] != '.':
        for info in tree:
            if info[0] == node[1]:
                in_order(info, _tree)
    print(node[0], end='')
    if node[2] != '.':
        for info in tree:
            if info[0] == node[2]:
                in_order(info, _tree)


def post_order(node, _tree):
    if node[1] != '.':
        for info in tree:
            if info[0] == node[1]:
                post_order(info, _tree)
    if node[2] != '.':
        for info in tree:
            if info[0] == node[2]:
                post_order(info, _tree)
    print(node[0], end='')


if __name__ == '__main__':
    N = int(input())
    tree = []
    for _ in range(N):
        tree.append(list(input().split()))

    pre_order(tree[0], tree)
    print()
    in_order(tree[0], tree)
    print()
    post_order(tree[0], tree)

🤔 회고

처음에는 이진 트리를 이용해서 문제를 풀려고 했지만 크기를 비교하는 개념이 없어서 오히려 더 시간이 오래 걸릴 것 같았다. 배열로 짜는게 더 시간을 아낄 수 있어서 배열로 문제를 해결했다.