Python으로 푸는 백준 1991. 트리 순회

1991 트리 순회

이 문제는 트리의 구조를 입력받아, 트리를 순회하는 전휘, 중위, 후위 순회 방식대로 값을 출력하는 문제이다. 트리의 기본 문제라고 할 수 있다.

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

github에서 코드 보기

문제 풀이

트리의 순회하는 방법으로는 전위 순회, 중위 순회, 후위 순회가 있다. 백준 1991 문제는 이진 트리의 순회에 관한 매우 기본적인 문제이다. 그럼에도 이 문제를 풀면서 난 매우 고전을 했다. 아무래도 트리를 구현하고나서 순회를 진행해야 하는데 트리를 구현하는 방식을 너무 쉽게 생각한 듯 하다.

1. 트리를 list(배열)로 구현한 방식 - 메모리 초과로 실패

내가 처음으로 푼 방법은 트리를 list(배열)로 구현한 방식이다. 문제에서 제안한 노드의 수는 최대 26개인데, 트리의 구조가 최악일 경우 level이 26일테고 이걸 리스트로 구현할 경우에는 최대 2^26 -1 개 만큼의 공간이 필요하게 된다. 나는 처음에 이게 과연 얼마나 큰 것인지 가늠을 하지 못했다. 26개이 노드이고 sys.getsizeof(['A'])로 측정한 사이즈 하나짜리의 리스트의 메모리의 크기는 72 bytes, 최대 2^26개의 메모리 공간이 필요하게 되는데 2^26 * 0.0703125KB(72 bytes) = 4718592KB = 4608MB 이다. 문제에서 메모리 제한이 128MB 였으므로 메모리 초과가 나올 수밖에 없었다. 리스트로 트리를 구현하게되면 리프노드의 경우에도 자식 노드가 비어 있음을 표현해주기 위해서 메모리 공간을 차지하게 되는데, 그때문에 불필요한 메모리가 많이 낭비되게 된다. 코드를 보고 헷갈리지 않게 말을 덧붙이자면, 아래 파이썬 코드에서 혹시 메모리를 줄일 수 있을까하여 list에 값을 추가한 후, ''.join()으로 string으로 변환시켜보았는데 생각해보니 값을 넣는 과정에서 이미 메모리 공간을 초과하였으므로 큰 효과는 없는 코드였다. 이 문제를 해결하기 위해서 dict를 활용해서 문제를 다시 풀게 되었다. 

2. 트리를 dict로 구현한 방식 - 성공

dict로 구현할 경우에는 입력받는 부분을 컨테이너에 담기가 편하다. 

노드의 값 : [왼쪽 노드의 값, 오른쪽 노드의 값]

형태로 저장되는 dict의 원소의 수는 최대 26개이며, 이는 list로 생성한 것보다 메모리를 훨씬 덜 차지한다. dict에서 key를 가지고 값을 찾아가는데는 O(1) 밖에 걸리지 않는다. 기존 코드를 활용해서 왼쪽 노드와 오른쪽 노드를 찾아가는 방식만 dict에서 찾도록 바꿔주면 문제는 쉽게! 풀린다. 만약, 이 문제를 풀다가 원인을 모르는 런타임 에러가 난다면 노드의 수가 1개인 경우를 고려해보자. 즉, 노드가 루트 'A'만 존재하는 경우이다. 이 부분을 고려해서 문제를 풀면 거의 대부분 문제 없이 문제를 맞출 수 있을 것 같다.

파이썬 코드 - 성공, dict 사용

import sys
input = sys.stdin.readline
 
# 전위 순회 (루트) (왼쪽 자식) (오른쪽 자식)
def preorder(tree, root):
    stack = []
    stack.append(root)
    result = ''
    while 0 < len(stack):
        data = stack.pop()
        result += data
 
        # 오른쪽 자식 노드 체크
        if tree[data][1] != '.':
            stack.append(tree[data][1])
 
        # 왼쪽 자식 노드 체크
        if tree[data][0] != '.':
            stack.append(tree[data][0])
    print(result) # ABDCEFG
 
 
# 중위 순회 (왼쪽 자식) (루트) (오른쪽 자식)
def inorder(tree, root):
    stack = []
    result = ''
    data = root
    stack.append(root)
    while True:
        # 왼쪽 자식 노드
        while tree[data][0] != '.':
            if data not in result:
                stack.append(tree[data][0])
                data = tree[data][0]
            else:
                break
 
        if 0 < len(stack):
            # 'D'
            data = stack.pop()
            result += data
            if tree[data][1] != '.':
                stack.append(tree[data][1])
                data = tree[data][1]
        else:
            break
    print(result) # DBAECFG
 
 
# 후위 순회 (왼쪽 자식) (오른쪽 자식) (루트)
def postorder(tree, root):
    stack = []
    result = ''
    stack.append(root)
    data  =root
 
    while True:
        # 왼쪽 자식 체크
        while tree[data][0] != '.':
            if tree[data][0] not in result:
                stack.append(tree[data][0])
                data = tree[data][0]
            else:
                break
 
        # 오른쪽 자식이 존재하는지를 먼저 체크하기 위해 pop() 하지 않고 값만 가져온다.
        last_data = stack[-1]
 
        # 오른쪽 자식이 존재하는지 체크
        if tree[last_data][1] == '.':
            # 오른쪽 자식이 없으면 그냥 출력
            result += stack.pop()
 
            # 다음 데이터를 지정해준다
            if stack:
                data = stack[-1]
            else:
                # stack이 비어 있으면 종료
                break
        else:
            # 오른쪽 자식이 있으면 다음의 규칙대로 해결
            #
            # 오른쪽 자식이 아직 나오지 않은 노드 -> stack에 추가
            if tree[data][1] not in result:
                stack.append(tree[data][1])
                data = tree[data][1]
            else:
                # 오른쪽 자식이 이미 나온 노드 -> 현재의 노드를 출력하고 start_index를 stack에 들어있는 노드로 바꿔준다.
                result += stack.pop()
                if 0 < len(stack):
                    data = stack[-1]
                else:
                    break
    print(result) # DBEGFCA
 
 
def solve(tree, root):
    preorder(tree, root) # ABDCEFG
    inorder(tree, root) # DBAECFG
    postorder(tree, root) # DBEGFCA
 
if __name__ == "__main__":
    n = int(input().strip())
    tree = {}
    root = None
    for i in range(n):
        info = input().strip().split(' ')
        tree[info[0]] = [info[1], info[2]]
 
    solve(tree, 'A')

 

파이썬 코드 - 실패, 메모리 초과, 배열 사용

import sys
import math
input = sys.stdin.readline
 
def preorder(tree):
    stack = []
    stack.append(tree[0])
    result = ''
    while 0 < len(stack):
        data = stack.pop()
        result += data
        index = tree.index(data)
 
        # 오른쪽
        if tree[2 * index + 2] != '.':
            stack.append(tree[2 * index + 2])
 
        # 왼쪽
        if tree[2*index + 1] != '.':
            stack.append(tree[2*index + 1])
    print(result) # ABDCEFG  (루트) (왼쪽 자식) (오른쪽 자식)
 
 
def inorder(tree):
    stack = []
    result = ''
    start_index = 0
    stack.append(tree[start_index])
    while True:
        while tree[2 * start_index + 1] != '.':
            stack.append(tree[2 * start_index + 1])
            start_index = 2*start_index + 1
        # stack ['A', 'B', 'D']
 
        if 0 < len(stack):
            # 'D'
            data = stack.pop()
            result += data
            index = tree.index(data)
            if tree[2*index + 2] != '.':
                stack.append(tree[2*index + 2])
                start_index = 2*index + 2
        else:
            break
    print(result) # DBAECFG  (왼쪽 자식) (루트) (오른쪽 자식)
 
 
 
def postorder(tree):
    stack = []
    result = ''
    start_index = 0
    stack.append(tree[start_index])
 
    while True:
        # 왼쪽 자식 체크
        while tree[2 * start_index + 1] != '.':
            if tree[2 * start_index + 1] not in result:
                stack.append(tree[2 * start_index + 1])
                start_index = 2*start_index + 1
            else:
                break
 
        # 오른쪽 자식이 존재하는지를 먼저 체크하기 위해 pop() 하지 않는다
        last_data = stack[-1]
        index = tree.index(last_data)
 
        # 오른쪽 자식이 존재하는지 체크
        if tree[2*index + 2] == '.':
            # 오른쪽 자식이 없으면 그냥 출력
            result += stack.pop()
            start_index = index
        else:
            # 오른쪽 자식이 있으면 다음의 규칙대로 해결
            #
            # 오른쪽 자식이 아직 나오지 않은 노드 -> stack에 추가
            if tree[2 * index + 2] not in result:
                stack.append(tree[2 * index + 2])
                start_index = 2 * index + 2
            else:
                # 오른쪽 자식이 이미 나온 노드 -> 현재의 노드를 출력하고 start_index를 stack에 들어있는 노드로 바꿔준다.
                result += stack.pop()
                if 0 < len(stack):
                    data = stack[-1]
                    start_index = tree.index(data)
                else:
                    break
 
    print(result) # DBEGFCA (왼쪽 자식) (오른쪽 자식) (루트)
 
 
def solve(tree):
    preorder(tree) # ABDCEFG
    inorder(tree) # DBAECFG
    postorder(tree) # DBEGFCA (왼쪽 자식) (오른쪽 자식) (루트)
 
 
 
if __name__ == "__main__":
    n = int(input().strip())
    tree = ['.']* int(math.pow(2, n))
    for i in range(n):
        info = input().strip().split(' ')
        if tree[0] == '.':
            tree[0], tree[1], tree[2] = info[0], info[1], info[2]
            continue
 
        root = info[0]
        idx = tree.index(str(root))
        tree[2*idx + 1] = info[1]
        tree[2*idx + 2] = info[2]
    tree = ''.join(tree)
    solve(tree)