백준 알고리즘 No.1991 트리 순회

in Study #Algorithm #Python

문제

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

(중략)

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

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

입력

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

출력

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



체감 난이도: ★★

이번 주차 대부분의 문제가 트리 순회에 관한 문제였는데, 순회 문제들 중에서 아이디어를 생각하는 과정은 어려웠지만 방법을 알고나면 쉬운 문제? 였던 것 같다. (문제에 힌트가 다 있다!!)

Code

def pre_order(root):  # 전위 순회 함수
    if root != '.':
        print(root, end='')
        pre_order(graph[root][0])
        pre_order(graph[root][1])


def in_order(root):   # 중위 순회 함수
    if root != '.':
        in_order(graph[root][0])
        print(root, end='')
        in_order(graph[root][1])


def post_order(root):   # 후위 순회 함수
    if root != '.':
        post_order(graph[root][0])
        post_order(graph[root][1])
        print(root, end='')


n = int(input())
graph = {}    # graph는 딕셔너리 형태

for _ in range(n):
    node, left, right = map(str, input().split())
    graph[node] = [left, right]

pre_order('A')
print()
in_order('A')
print()
post_order('A')

Solution

우선 graph를 딕셔너리 형태(각 노드를 key, 자식 노드들을 value)로 가져온다.
딕셔너리를 사용한 이유는 효율적으로 자식 노드들을 관리하기 위함이다.

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

문제의 설명대로 각 함수의 구조를 만든 다음, 각 함수들을 재귀적으로 호출한다.

예를 들어, pre_order(전위 순회) 함수의 구조는 다음과 같다.

def pre_order(root):
    if root != '.':               # 자식 노드가 있다면,
        print(root, end='')       # (루트)
        pre_order(graph[root][0]) # (왼쪽 자식)
        pre_order(graph[root][1]) # (오른쪽 자식)

같은 방식으로 나머지 함수들도 만들어주면 된다.


혹시 더 좋은 알고리즘 풀이가 있다면 언제든 댓글로 알려주세요 😃