백준 1991: 트리순회

출처

백준 1991

문제요약

노드 정보가 문자열로 주어졌을 때 트리로 그린 후 순회를 하는 문제입니다. 입력값으로 각 노드의 값과 자식노드에 대한 정보가 주어집니다.

접근법

문자열의 첫번째 값을 노드의 키로 보고 뒤의 두 값들을 노드의 자식노드로 봅니다.
노드간의 관계를 딕셔너리로 표현합니다.
딕셔너리를 토대로 트리 순회를 구현합니다.

나의 코드

from typing import Any
import sys

N = int(sys.stdin.readline().strip())

tree = {}

for i in range(N):
    node = [x for x in sys.stdin.readline().split()]
    tree[node[0]] = [node[1], node[2]]


def preorder(root: str = "A", tree: dict = tree) -> None:
    parent = tree[root]
    print(root, end="")
    left = parent[0]
    right = parent[1]
    if left != ".":
        preorder(left)
    if right != ".":
        preorder(right)


def inorder(root: str = "A", tree: dict = tree) -> None:
    parent = tree[root]
    left = parent[0]
    right = parent[1]
    if left != ".":
        inorder(left)
    print(root, end="")
    if right != ".":
        inorder(right)


def postorder(root: str = "A", tree: dict = tree) -> None:
    parent = tree[root]
    left = parent[0]
    right = parent[1]
    if left != ".":
        postorder(left)
    if right != ".":
        postorder(right)
    print(root, end="")


preorder()
print()
inorder()
print()
postorder()
print()

활용개념

트리의 구조

트리 순회를 문제를 풀려면 트리에 대한 개념이 필요합니다. 트리는 계층구조를 가진 데이터의 자료구조입니다. 트리는 루트노드를 시작으로 리프노드를 향해 계층구조를 이룹니다. 트리는 배열 또는 연결리스트로 구현하는 것이 보통입니다. 이번에는 사전을 활용해서 구현하는 것이 신선했습니다.

트리의 순회

트리는 순회방식에 따라 bfs, dfs로 분류할 수 있습니다. 해당 문제의 경우, dfs의 세부내용인 전위, 중위, 후위순회에 대한 문제입니다.
전위순회는 (루트) - 왼쪽자식노드 - 오른쪽 자식노드 순으로 순회합니다.
중위순회는 왼쪽 - (루트) - 오른쪽 순으로 순회합니다.
후위순회는 왼쪽 - 오른쪽 - (루트) 순으로 순회합니다.

재귀함수

전위, 중위, 후위 순회는 재귀함수를 활용하면 간단하게 표현할 수 있습니다. 재귀함수란 함수 정의에 스스로를 호출하는 내용을 담는 함수입니다. 내부적으로 스택메모리에 쌓이기 때문에 거동이 스택과 사실상 동일합니다.

구현

트리의 구현

tree = {}

for i in range(N):
    node = [x for x in sys.stdin.readline().split()]
    tree[node[0]] = [node[1], node[2]]

사전을 활용해서 트리를 구현했습니다.

순회의 구현

def preorder(root: str = "A", tree: dict = tree) -> None:
    parent = tree[root]
    print(root, end="")
    left = parent[0]
    right = parent[1]
    if left != ".":
        preorder(left)
    if right != ".":
        preorder(right)


def inorder(root: str = "A", tree: dict = tree) -> None:
    parent = tree[root]
    left = parent[0]
    right = parent[1]
    if left != ".":
        inorder(left)
    print(root, end="")
    if right != ".":
        inorder(right)


def postorder(root: str = "A", tree: dict = tree) -> None:
    parent = tree[root]
    left = parent[0]
    right = parent[1]
    if left != ".":
        postorder(left)
    if right != ".":
        postorder(right)
    print(root, end="")

트리의 순회개념과 재귀함수를 활용하여 순회를 구현하였습니다.

참고문헌

위키독스
Implementation of Tree Data Structure