[백준] 2263번 : 트리의 순회

https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

해당 문제는 분할정복과 재귀를 사용하여 문제를 해결 하였습니다. 문제를 풀기 이전에 트리의 개념에 대하여 학습이 필요 합니다.

트리의 순회는 3가지가 있습니다. 선위순회(프리오더), 중위순회(인오더), 후위순회(포스트오더) 가 있습니다.

- 선위순회(프리오더) : 루트 노드 -> 왼쪽 노드 -> 오른쪽 노드 순으로 방문을 하는 방식

- 중위순회(인오더) : 왼쪽 노드 -> 루트 노드 -> 오른쪽 노드 순으로 방문을 하는 방식

- 후위순회(포스트오더) : 왼쪽 노드 -> 오른쪽 노드 -> 루트 노드 순으로 방문을 하는 방식

문제에서 중위순회외 후위순회가 주어졌을때 선위순회를 출력해야 합니다.

 

여기서 중위순회와 후위순회의 성질을 이용하여 분할정복하여 문제를 해결합니다.

후위순회의 마지막은 항상 루트 노드 입니다. 중위순회는 루트노드를 기준으로 왼쪽노드그룹 오른쪽 노드그룹으로 나뉠 수 있습니다.

여기서 중위순회에서 왼쪽노드 그룹으로, 오른쪽 노드그룹으로 나누는 것이 분할정복을 사용하여 문제를 접근 할 수 있습니다.

 

예를들어 다음과 같이 주어진다고 가정한다면

후위순회 : 8 4 9 2 5 1 6 3 7
중위순회 : 8 9 4 5 2 6 7 3 1

후위순회는 마지막 노드가 루트노드이니

첫번째 분할 :

루트노드 : 7

왼쪽 노드 그룹 : 8 9 4 5 2 6

오른쪽 노드 그룹 : 3 1

 

선위순회를 출력해야하니, 왼쪽노드 그룹부터 재귀적으로 분할정복하고, 그 이후에 오른쪽 노드 그룹을 재귀적으로 분할정복하면 문제를 해결 할 수 있습니다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))

rootindex = [0 for _ in range(n+1)]
for i in range(n):
    rootindex[inorder[i]] = i

def newgetPredorder(startin, endin, startpost, endpost):
    if startin > endin or startpost > endpost:
        return
    
    root = postorder[endpost]
    idx = rootindex[root]
    print(root, end= ' ') # 루트 노드 출력
    
    newgetPredorder(startin, idx-1, startpost, startpost - startin + idx-1) # 좌측 노드 출력
    newgetPredorder(idx+1, endin, endpost - endin + idx, endpost-1) # 우측 노드 출력
    
    
def getPreorder(inorder, postorder):
    # 배열의 길이가 1이 되면 종료
    if inorder and postorder:
        if len(inorder) == 1:
            print(inorder[0], end= ' ')
            return

        rootnode = postorder[-1]
        rootidx = inorder.index(rootnode)
        
        # 프리오더는 루트노드, 좌측노드, 우측노드를 출력한다.
        print(postorder[-1], end= ' ') # 루트노드출력
        getPreorder(inorder[:rootidx], postorder[:rootidx]) # 좌측노드 출력
        getPreorder(inorder[rootidx+1:], postorder[rootidx:len(postorder)-1]) # 우측노드 출력
    
#getPreorder(inorder, postorder)
newgetPredorder(0, n-1, 0, n-1)

처음 문제를 풀때 파이썬 리스트 컴프리핸션을 이용한 배열 슬라이싱을 하여 문제를 해결 하였으나, 메모리 복잡도에서 걸렸습니다. ( 많은 배열을 재귀 호출)

 

그 이후 저는 start, end 를 사용하여 숫자로 슬라이싱 하여 문제를 해결 하였습니다.

 

추가로 트리를 순회 할때 잘못 된 범위로 순회를 하였는데

newgetPredorder(startin, idx-1, startpost, idx-1)

newgetPredorder(idx+1, endin, idx, endpost-1)

 

반례

n = 3

inorder = [2, 1, 3]

postorder = [2, 3, 1]

 

분할정복할때 left 리스트의 크기와 right리스트의 크기를 사용하여 해결 하였습니다.