백준 5639번_이진 검색 트리(Python)

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

 

코드

import sys
sys.setrecursionlimit(10**6)
INF = 10**8

fSearch = []
while(1):
    try:
        fSearch.append(int(input()))
    except:
        break
l = len(fSearch)
lower = [[-1]*2 for _ in range(l)]

currentIndex = -1
def makeTree(maxiLeft, miniRight):
    global currentIndex
    currentIndex += 1
    hereIndex = currentIndex
    if currentIndex <= l-2 and miniRight < fSearch[currentIndex+1] < fSearch[hereIndex]:
        lower[hereIndex][0] = currentIndex+1
        makeTree(fSearch[hereIndex], miniRight)
    if currentIndex <= l-2 and maxiLeft > fSearch[currentIndex+1] > fSearch[hereIndex]:
        lower[hereIndex][1] = currentIndex+1
        makeTree(maxiLeft, fSearch[hereIndex])

def backTrack(k):
    if lower[k][0] != -1:
        backTrack(lower[k][0])
    if lower[k][1] != -1:
        backTrack(lower[k][1])
    print(fSearch[k], end = ' ')

makeTree(INF, 0)
backTrack(0)

 

풀이

우선 전위 순회와 후위 순회가 어떻게 진행되는 것인지 정확히 파악할 필요가 있다.

먼저 전위 순회의 케이스에서, 위의 예시를 보면 노드 '30'은 우선 본인, 그다음은 자기보다 작은 수들의 모임인 왼쪽 가지(24, 5, 28), 그다음은 자기보다 큰 수들의 모임인 오른쪽 가지(45)의 순서로 순회를 진행한다. 다른 노드들을 비교해 보아도 이런 방식은 동일하다. 즉, 위 문제에서 정의된 전위 순회의 규칙이 모든 노드에 대해서 점화식처럼 적용된다는 것을 알 수 있다. 후위 순회도 마찬가지다. 따라서 이런 경우에는 각각의 노드에 대해서 이 '점화식'을 반복해서 실행해주는 재귀함수를 사용해주는 것이 맞을 것이다.

 

함수 두 개가 있다. 우선, makeTree는 입력받은 전위 순회를 기준으로 트리를 만드는 함수다. makeTree에서 사용되는 전역변수 currentIndex는 전위 순회열 fSearch의 0부터 currentIndex까지 현재 탐색했다는 의미다. 즉, 함수 초기에는 currentIndex를 이용해 해당 함수의 재귀가 어느 노드를 다루는지 알 수 있다. 코드에서 currentIndex += 1이 현재 노드를 방문했음을 표시하는 동시에 현재 노드의 번호를 확인한다. 이때 왼쪽, 오른쪽 두번 재귀를 돌릴 것인데 한 번 재귀를 돌리면 currentIndex가 변해 현재 위치하는 노드의 번호를 잃어버리게 되어 이를 hereIndex에 저장한다.

 

전위 순회를 따라가면 현재 노드 다음에는 왼쪽 가지에 해당하는 노드들, 그다음은 오른쪽 가지에 해당하는 노드들이 나온다. 우선, 왼쪽 가지가 존재한다는 가정 하에, 현재의 왼쪽 노드가 바로 다음으로 탐색될 것이므로 그 번호는 currentIndex+1이 될 것이다. 이때 currentIndex+1번째 전위 순회 노드는 무조건 현재 노드보다 크기가 작아야 한다.

또한, 왼쪽 가지를 전부 탐색하고 나면 왼쪽 가지에 속하는 마지막 노드의 번호가 currentIndex에 저장될 것이다. 왼쪽 가지를 전부 탐색한 뒤는, 오른쪽 가지가 존재한다는 가정 하에 현재의 오른쪽 노드가 탐색될 것이고, 그 번호는 currentIndex+1이 될 것이다. 이때도 currentIndex+1번째 전위 순회 노드는 무조건 현재 노드보다 크기가 커야 한다.

트리는 나중에 재귀를 이용하여 후위 순회를 쉽게 찾기 위해 lower라는 배열에 각 노드의 왼쪽 노드, 오른쪽 노드를 저장하는 방식으로 구축한다.

 

이때 단순히 currentIndex+1번째 전위 순회 노드와 현재 노드의 크기만 비교하면 오류가 생길 수 있다. 예를 들어 위의 전위 순회 50 30 24 5 28 45 98 52 60를 보자. 50에서 시작한 후 트리는 다음과 같이 구현된다.

위 트리의 문제는 24보다 큰 28이 24의 왼쪽 가지에 저장되면서 시작된다. 또한, 이 '28'은 30보다 작으면서 30의 왼쪽 가지에 저장되기도 했다. 이런 문제를 방지하기 위해, 다음과 같은 조건을 추가적으로 걸어줘야 한다.

• 어떤 노드가 현재 노드의 왼쪽 노드가 되려면 출발점부터 현재 노드까지의 경로를 생각했을 때, 경로에 포함된 간선이 오른쪽 노드와 연결되어있는 노드들보다 무조건 크기가 커야 한다.
• 어떤 노드가 현재 노드의 오른쪽 노드가 되려면 출발점부터 현재 노드까지의 경로를 생각했을 때, 경로에 포함된 간선이 왼쪽 노드와 연결되어있는 노드들보다 무조건 크기가 작아야 한다.

각 조건을 분석해서 생각해보자.

A라는 노드가 현재 노드의 크기보다 작아 현재 노드의 왼쪽 노드가 되는 것을 고려하고 있다. 이때 출발점에서 현재 노드까지 온 경로를 봤는데, B'라는 노드에서 그 오른쪽 노드인 B라는 노드로 이동한 경로가 있다고 하자. 즉, B'의 크기보다 B 및 그 하위 노드들의 크기가 더 큼을 의미하다. B의 하위 노드에 A도 포함되므로, A의 크기는 B'의 크기보다 커야 한다.

반대로 A라는 노드가 현재 노드의 크기보다 큰 경우, 현재 노드의 오른쪽 노드가 될 것이다. 이때 출발점에서 현재 노드까지 온 경로에서, B'라는 노드에서 그 왼쪽 노드인 B라는 노드로 이동한 경로가 있을 수 있다. 즉, B'의 크기보다 B 및 그 하위 노드들의 크기가 더 작아야 한다. B의 하위 노드에 A도 포함되므로, A의 크기는 B'의 크기보다 작아야 한다.

따라서 makeTree의 두 파라미터 maxiLeft는 이때까지의 경로들 중 자신의 왼쪽 노드로 탐색을 이어간 노드들의 크기들의 최솟값, 즉 현재 노드에서 오른쪽 노드가 가질 수 있는 최댓값을 제한하는 변수다. 또한, miniRight는 이때까지의 경로들 중 자신의 오른쪽 노드로 탐색을 이어간 노드들의 크기들의 최댓값, 즉 현재 노드에서 왼쪽 노드가 가질 수 있는 최솟값을 제한하는 변수다.

이 조건까지 포함하면 원하는 트리를 제대로 구축할 수 있다.

 

 

두 번째 함수 backTrack는 후위 순회를 하는 재귀함수다. 맨 앞에서 말했던 순회의 '점화식'을 철저히 따르면 된다. 우선, 트리에서 자신의 왼쪽 가지를 탐색하도록 backTrack(현재의 왼쪽 노드)를 실행한다. 그 뒤, 트리에서 자신의 오른쪽 가지를 탐색하도록 backTrack(현재의 오른쪽 노드)를 실행한다. 그 뒤, 두 재귀가 모두 실행된 뒤에는 자신까지 탐색(출력)하고 나서 함수를 종료한다.