백준 1991번 트리 순회

서론

1991번: 트리 순회

예전에 배워서 알고 있는 개념이긴 했는데 잘 기억이 나지 않아서 이번 기회에 다시 공부하면서 정리합니다. 트리순회는 아래와 같은 세 가지 방법이 있습니다.

1. Preorder 전위 순회: root => left => right
2. Inorder 중위 순회: left => root => right
3. Postorder 후위 순회: left => right => root

그리고 각자의 left, rigt가 트리라면 다시 그곳에서 같은 방법으로 순회를 하면 됩니다. 설명에서도 알 수 있듯이 명백하게 재귀를 이용하면 쉽게 풀리는 문제입니다.

제한 조건

• 시간제한 - 2초

시간제한은 2초입니다. 일반적인 컴퓨터로 1초에 1억 번 연산한다는 기준을 가지고 풉니다. 지금까지 앞의 문장을 계속 사용하면서 무언가 for문이나 que안에 있는 노드들을 탐색하면서 연산에 대한 횟수만 중요하게 생각했는데 아래 코드처럼 재귀함수로 새로운 함수를 계속 호출하는 경우는 계산을 어떻게 해야 하는지를 잘 모르겠습니다.

데이터를 스택에 넣고(push) 꺼내는(pop) 데에는 시간이 소비됩니다. 재귀 알고리즘은 최소 O(n)의 공간을 사용합니다. 여기서 n은 재귀 호출의 깊이(depth)입니다.

찾아보니 위와 같은 내용이고 최소 O(n)이라는것은 재귀함수 안에서의 시간복잡도가 O(1)일 경우 일 것 같습니다. 따라서 제 코드도 O(n)이 되겠습니다. 여기서 n은 노드의 개수인데 문제에선 최대가 26입니다. 시간제한을 왜 2초나 준걸까요?

• 메모리 제한 - 128MB

메모리 제한은 128MB입니다. 역시 재귀함수에서의 메모리 제한도 생각해본 적이 없지만, 직관적으로 그냥 재귀할 때마다 사용한 메모리가 차지할 것 같습니다. 이 부분은 딱히 문제가 안 되는 것 같습니다.

모든 재귀 호출에 대해 재귀함수는 인수, 반환 주소, 지역 변수를 메모리의 스택에 할당합니다.

역시 찾아보니 위와 같이 쓰여져 있는데 생각한 대로라서 문제없습니다. 전체 노드의 개수와 노드가 담고 있는 edge 정보가 메모리를 차지할 텐데 역시 시간과 마찬가지로 128MB까지 필요 없을 거 같습니다.

Tree traversal (recursive)

순회의 개념만 알고 있다면 아래 코드가 굉장히 직관적입니다. 바로 이해할 수 있습니다.

from collections import deque as dq
import sys
input = sys.stdin.readline

N = int(input())

graph = {}
for i in range(N):
    root, left, right = input().split()
    if root not in graph.keys():
        graph[root] = []
    graph[root].append(left)
    graph[root].append(right)


# root first
def preorder(chr):
    print(chr, end='')
    if graph[chr][0] != '.':
        preorder(graph[chr][0])
    if graph[chr][1] != '.':
        preorder(graph[chr][1])


# left tree => root
def inorder(chr):
    if graph[chr][0] != '.':
        inorder(graph[chr][0])
    print(chr, end='')
    if graph[chr][1] != '.':
        inorder(graph[chr][1])


# child(left=>right) => root
def postorder(chr):
    if graph[chr][0] != '.':
        postorder(graph[chr][0])
    if graph[chr][1] != '.':
        postorder(graph[chr][1])
    print(chr, end='')


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

Tree traversal (stack)

사실 재귀함수 자체가 스택이지만 뭔가 지금까지 풀어온 알고리즘으로 스택을 구현해서 푸는 방법도 있습니다. 쉬웠던 문제지만 어렵게도 돌아가 보고자 이 방법으로도 풀어보아서 올립니다.

from collections import deque as dq
import sys
input = sys.stdin.readline

N = int(input())

graph = {}
for i in range(N):
    root, left, right = input().split()
    if root not in graph.keys():
        graph[root] = []
    graph[root].append(left)
    graph[root].append(right)


# root first
def preorder(graph):
    que = dq()
    que.append('A')

    while que:
        node = que.pop()
        print(node, end='')
        for child in reversed(graph[node]):
            if child != '.':
                que.append(child)
    print()


# left tree => root
def inorder(graph):
    que = dq()
    que.append('A')
    visited = [False]*100
    visited[ord('.')] = True

    while que:
        node = que.pop()
        if visited[ord(graph[node][0])] and visited[ord(graph[node][1])]:
            print(node, end='')

        else:
            if not visited[ord(graph[node][1])]:
                que.append(graph[node][1])
                visited[ord(graph[node][1])] = True

            que.append(node)

            if not visited[ord(graph[node][0])]:
                que.append(graph[node][0])
                visited[ord(graph[node][0])] = True
    print()


# child(left=>right) => root
def postorder(graph):
    que = dq()
    que.append('A')
    visited = [False]*100
    visited[ord('.')] = True

    while que:
        node = que.pop()
        if visited[ord(graph[node][0])] and visited[ord(graph[node][1])]:
            print(node, end='')

        else:
            que.append(node)

            if not visited[ord(graph[node][1])]:
                que.append(graph[node][1])
                visited[ord(graph[node][1])] = True

            if not visited[ord(graph[node][0])]:
                que.append(graph[node][0])
                visited[ord(graph[node][0])] = True
    print()


preorder(graph)
inorder(graph)
postorder(graph)

생각

재귀함수 자체가 스택이라는 말이 컴퓨터에서 프로그램을 실행할 때 구조 자체가 스택이라는 뜻인데 이 부분이 저도 정확하게 기억이 나지 않아서 제대로 설명할 수가 없습니다. 다시 공부하도록 하겠습니다.