[BOJ_1991] 트리 순회 (python)

1991번: 트리 순회

 

크리스마스 이브를 맞아 트리 문제를 풀어보았습니다 푸헤헤 이 글을 보는 여러분 모두 메리크리스마스~~

 

✅ 문제 설명

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 문제입니다.

(이진 트리: 각 노드가 최대 2개의 자식노드를 가지는 트리)

 

전위순회, 중위순회, 후위순회?

전위순회 = (루트) (왼쪽 자식) (오른쪽 자식)

중위순회 = (왼쪽 자식) (루트) (오른쪽 자식)

후위순회 = (왼쪽 자식) (오른쪽 자식) (루트) 순으로 트리를 탐방하는 것입니다.

 

✅ 접근 방식

• 전위순회, 중위순회, 후위순회는 dfs로 구현이 가능합니다. 
• 보통 dfs는 전위 순회를 많이 사용합니다.

전위순회	깊이 우선 순회 (DFT, Depth-First Traversal)라고도 합니다. 트리를 복사하거나 전위순회를 할 때 주로 사용됩니다. 트리를 복사할 때 이를 사용하는 이유는 자식노드보다 부모노드가 먼저 생성되어야 하기 때문에 (루트) (왼쪽노드) (오른쪽노드) 순으로 탐방하는 전위순회를 사용합니다.
중위순회	(왼쪽 노드) (루트) (오른쪽 노드)로 대칭으로 보이기 때문에 대칭 순회(symmetric traversal)라고도 합니다. 이진 탐색트리에서 오름차순 또는 내림차순으로 값을 가져올 때 주로 사용됩니다. (왼쪽 노드) (루트) (오른쪽 노드) 순으로 순회하면 오름차순으로 값을 가져올 수 있고, (오른쪽  노드) (루트) (왼쪽  노드) 순으로 순회하면 내림차순으로 값을 가져올 수 있습니다.
후위 순회	후위 순회는 트리를 삭제하는데 주로 사용됩니다. 그 이유는 트리 생성과는 반대로 트리 삭제를 할때는 부모노드를 삭제하기 전에 자식 노드를 삭제하는 순으로 노드를 삭제해야하기 때문입니다.

 

이진 탐색 트리? 이진 탐색 트리는 이진트리에 "왼쪽 자식은 나보다 작고, 오른쪽 자식은 나보다 크다"는 규칙이 추가된, 탐색을 위한 이진 트리입니다.

 

✅ 코드 설명

트리 입력 받기

import sys

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

tree = dict()
for i in range(N):
    root, left, right = map(str, sys.stdin.readline().split())
    tree[root] = [left, right]

앞 포스트에서 트리를 구성할 때 썼던, 인접리스트 형태로 트리를 구현해주었습니다.

다만 이때 왼쪽 노드, 오른쪽 노드에 대한 정보가 필요하므로 마구잡이로 넣지 않고 순서를 left, right로 넣어주었습니다.

또, 이번에는 graph = [set() for i in range(N)]로 구현했던 저번 포스트와 달리 dict()으로 tree를 선언하여 노드수만큼 초기값을 설정해줘야하는 귀찮음을 덜 수 있었습니다.

 

전위 순회 함수

def preorder(node):
    if node == '.':
        return
    print(node, end='')
    preorder(tree[node][0])
    preorder(tree[node][1])

(루트=node) (왼쪽 노드=tree[node][0]) (오른쪽 노드=tree[node][1]) 순으로 트리를 순회합니다. 

. 이면 해당노드가 없는 것이므로 함수를 종료합니다.

 

중위 순회 함수

def inorder(node):
    if node == '.':
        return
    inorder(tree[node][0])
    print(node, end='')
    inorder(tree[node][1])

(왼쪽 노드=tree[node][0]) (루트=node) (오른쪽 노드=tree[node][1]) 순으로 트리를 순회합니다. 

. 이면 해당노드가 없는 것이므로 함수를 종료합니다.

 

후위 순회 함수

def postorder(node):
    if node == '.':
        return
    postorder(tree[node][0])
    postorder(tree[node][1])
    print(node, end='')

(왼쪽 노드=tree[node][0]) (오른쪽 노드=tree[node][1]) (루트=node) 순으로 트리를 순회합니다. 

. 이면 해당노드가 없는 것이므로 함수를 종료합니다.

 

preorder('A')
print()
inorder('A')
print()
postorder('A')

문제에서 A가 루트노드가 된다고 했으므로 A부터 전위 순회, 중위순회, 후위순회를 실시합니다.

 

✅ 최종 코드

# 트리 순회

import sys

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

tree = dict()
for i in range(N):
    root, left, right = map(str, sys.stdin.readline().split())
    tree[root] = [left, right]


def preorder(node):
    if node == '.':
        return
    print(node, end='')
    preorder(tree[node][0])
    preorder(tree[node][1])


def inorder(node):
    if node == '.':
        return
    inorder(tree[node][0])
    print(node, end='')
    inorder(tree[node][1])


def postorder(node):
    if node == '.':
        return
    postorder(tree[node][0])
    postorder(tree[node][1])
    print(node, end='')


preorder('A')
print()
inorder('A')
print()
postorder('A')

 

❇️ 코멘트

• 전위 순회, 중위 순회, 후위 순회는 결국 트리를 순회할 때 트리의 구성요소인 (왼쪽 노드) (루트) (오른쪽 노드) 중에 방문할 순서를 어떻게 정하는지의 차이입니다.
• 루트노드가 가장 먼저 나오면 전위순회, 중간에 위치하면 중위순회, 젤 뒤에 위치하면 후위 순회입니다.
• 이번에 코드를 짜면서 전위순회, 중위순회, 후위순회가 dfs의 종류라면 내가 원래 알고 있던 dfs 코드와 왜 다르지?에 대해 고민해봤습니다. 그 결과 트리와 그래프에서의 dfs, bfs 코드 차이에 대해 알게되었습니다. 이에 대해선 이후에 자세히 포스팅하도록 하겠습니다 :)