백준 2263번: 트리의 순회

✔ 풀이를 위한 아이디어

• 자료구조 중 트리 (Tree), 그리고 트리 순회의 응용
• 분할 정복 (Divide-and-conquer algorithm)
• 재귀 (Recursion)
  
  

✔ 트리 순회 심화편

• 일반적인 트리 순회에 대한 개념은 다음 게시물을 참조하자 - https://hongku.tistory.com/160

• 후위 순회 (Postorder traverse) 에서 우리가 쉽게 알 수 있는 것은, 맨 마지막에 루트 노드의 데이터가 오게 된다는 것이다.

• 이를 통해, 중위 순회 (Inorder traverse) 에서 루트 노드를 찾을 수 있고, 중위 순회의 특성상 왼쪽에서 오른쪽으로 진행하므로, 루트 노드를 기준으로 왼쪽 오른쪽의 sub tree로 나눌 수 있다. (좌측 그림 참조)

• 나눠진 sub tree를 후위 순회의 결과에서 찾아보면, 역시 함께 묶여있음을 확인할 수 있다. 이 각 묶음에서도 맨 마지막에 오는 데이터가 루트 노드에 해당한다. (우측 그림 참조)

• 이러한 과정을 계속해서 반복 (Recursion) 하며 중위 순회와 후위 순회의 결과를 쪼개나가면 (Divide-and-conquer) 전체 Tree를 밝혀낼 수 있다.
  
  

✔ 정답 코드

import sys
sys.setrecursionlimit(10**6)  #  파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕은 편이므로 필수

n = int(sys.stdin.readline())
inOrder = list(map(int, sys.stdin.readline().split()))
postOrder = list(map(int, sys.stdin.readline().split()))

directInOrder = [-1]*(n+1)
for i in range(n):
    directInOrder[inOrder[i]] = i

def fillTree(stIndx_i, edIndx_i, stIndx_p, edIndx_p, currentRoot):
    currentRoot['data'] = postOrder[edIndx_p]
    mid = directInOrder[postOrder[edIndx_p]]

    if stIndx_i < mid:
        leftRoot = {}
        currentRoot['left'] = leftRoot
        fillTree(stIndx_i, mid-1, stIndx_p, stIndx_p+(mid-stIndx_i-1), leftRoot)

    if mid < edIndx_i:
        rightRoot = {}
        currentRoot['right'] = rightRoot
        fillTree(mid+1, edIndx_i, edIndx_p-(edIndx_i-mid), edIndx_p-1, rightRoot)


def preOrder(currentRoot):
    print("{} ".format(currentRoot['data']), end="")
    if 'left' in currentRoot:
        preOrder(currentRoot['left'])
    if 'right' in currentRoot:
        preOrder(currentRoot['right'])


ultimateRoot = {}
fillTree(0, n-1, 0, n-1, ultimateRoot)
preOrder(ultimateRoot)
print()

위에서 설명한 원리에 따라, 분할 정복 (Divide-and-conquer algorithm) 과 재귀 (Recursion) 를 활용해 작성한 코드는 위와 같다. 지금부터 이 코드를 부분별로 나누어 설명하도록 하겠다.

• directInOrder 정의
  매번 inOrder 배열을 탐색하는 것은 시간복잡도를 증가시키므로, 아래와 같이 처리하여 inOrder의 각 data들이 몇 번째 index에 있는지 한번에 알 수 있도록 한다.

directInOrder = [-1]*(n+1)
for i in range(n):
    directInOrder[inOrder[i]] = i  

• fillTree 정의
  재귀적으로 호출되며, Tree를 밝혀내는 함수이다. 4가지 변수를 활용해 배열을 분할하고, 전체 Tree를 정복한다.

def fillTree(stIndx_i, edIndx_i, stIndx_p, edIndx_p, currentRoot):
    # stIndx_i, edIndx_i: inOrder 배열에서 살펴볼 곳의 시작점과 끝점
    # stIndx_p, edIndx_p: postOrder 배열에서 살펴볼 곳의 시작점과 끝점
   
    currentRoot['data'] = postOrder[edIndx_p]
    mid = directInOrder[postOrder[edIndx_p]]

    if stIndx_i < mid:
        leftRoot = {}
        currentRoot['left'] = leftRoot
        fillTree(stIndx_i, mid-1, stIndx_p, stIndx_p+(mid-stIndx_i-1), leftRoot)

    if mid < edIndx_i:
        rightRoot = {}
        currentRoot['right'] = rightRoot
        fillTree(mid+1, edIndx_i, edIndx_p-(edIndx_i-mid), edIndx_p-1, rightRoot)

1. 우선, InOrder 배열과 postOrder 배열에서 살펴봐야할 부분이 계속해서 바뀌므로 총 4개의 parameter을 활용해 각 재귀호출에서 알 수 있도록 한다.
   또한, 루트 노드부터 시작해 sub tree의 루트 노드들로 내려가며 전체 Tree를 밝혀나가는 흐름이므로 , 현재의 루트 노드도 같이 넘겨준다.

2. 후위 순회의 맨 마지막 값이 현재의 루트 노드의 data에 해당하므로, 값을 넣어준다.
   또한, 현재 루트노드의 값이 InOrder에서 몇번째 index에 있는지를 파악하여 mid라는 변수에 넣어준다.

3. 살펴볼 inOrder 배열의 범위에서 루트 노드 왼쪽에 data가 있다면 좌측 자식 노드를 만들 수 있으므로, 새로운 dictionary를 만들어서 넣어준다.
   이때, 다음에 inOrder에서 살펴볼 부분은 현재 루트 노드의 왼쪽이므로 stIndx_i와 mid-1을 넘겨준다.
   또한, 다음에 postOrder에서 살펴볼 부분은 기존에 살펴보던 시작점부터, inOrder에서 살펴볼 부분의 크기만큼 (mid-1-stIndx_i) 이므로 위와 같이 넘겨준다.

4. 살펴볼 inOrder 배열의 범위에서 루트 노드 오른쪽에 data가 있다면 우측 자식노드를 만들 수 있으므로, 새로운 dictionary를 만들어서 넣어준다.
   이때, 다음에 inOrder에서 살펴볼 부분은 현재 루트 노드의 오른쪽이므로, mid+1과 edIndx_i를 넘겨준다.
   또한, 다음에 postOrder에서 살펴볼 부분은 기존에 살펴보던 끝점에서 하나를 뺀 edIndx_p-1부터, inOrder에서 살펴볼 부분의 크기만큼이므로 위와 같이 넘겨준다.

• preOrder 정의
  재귀적으로 전위 순회 하며 순서대로 data를 출력하는 함수이다. dictionary에 key값이 있는지 확인할 때는 아래와 같이 처리한다.

def preOrder(currentRoot):
    print("{} ".format(currentRoot['data']), end="")
    if 'left' in currentRoot:
        preOrder(currentRoot['left'])
    if 'right' in currentRoot:
        preOrder(currentRoot['right'])

• main부 정의
  처음에는, 전체 배열을 살펴보며 시작하므로 0과 n-1을 넘겨준다. 또한, 루트 노드 역할을 할 dictionary를 선언하고 fillTree 함수에 넘겨주어, Tree가 완성되도록 한다. 이후 이 루트 노드를 preOrder 함수에 넣어서 정답을 출력한다.

ultimateRoot = {}
fillTree(0, n-1, 0, n-1, ultimateRoot)
preOrder(ultimateRoot)
print()

• 처음에는 위에서 설명한 원리들을 완벽히 구현하지 않았기 때문에 틀렸으며, RecursionError은 setrecursionlimit 메서드를 활용해 쉽게 해결하였다.

• 문제를 푸는데 활용한 반례들: https://bingorithm.tistory.com/5