백준 문제풀기 [#5639번] - 이진 검색 트리 with Python

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

5639번: 이진 검색 트리

---

⚠️ 문제 

 

✍ 풀이 

전위 순회순으로 입력된다. ( 루트 노드 -> 왼쪽 자식노드 -> 오른쪽 자식 노드 ) 

전위 순회는 첫 번째 입력되는 값은 항상 최상단의 루트 노드일 것이다. 

 그 후 두번째 값부턴 최상단 루트 노드를 기준으로 왼쪽 자식 노드일 것이다.

이때 문제에서 주어진 이진 트리는 왼쪽 서브 트리가 루트 노드보다 작고, 오른쪽 서브 트리는 루트 노드보다 크다는 것이다. 

즉, 최상단 루트의 값을 기준으로  큰 값이 나오기 전까지는 왼쪽 자식 노드일 것이고, 큰 값이 나온 이후로는 오른쪽 노드일 것이다. 

 

1. 50 30 24 5 28 45 98 52 60 
빨간색 : 최상단 루트 노드 
파랑색: 왼쪽 자식 노드 
초록색 : 오른쪽 자식 노드

 

이렇듯 루트 노드 , 왼쪽 자식노드 , 오른쪽 자식노드를 구분해준 뒤, 후위 순회로 재조립하기 위해 재귀를 통해 왼쪽 서브트리를 먼저 끝까지 탐색하고 오른쪽 서브트리를 끝까지 탐색하고 루트를 출력한다. 

 

 

 

👩🏻‍💻 코드 

import sys
sys.setrecursionlimit(10 ** 9)  #재귀 호출의 최대 깊이를 설정


node = []

#엔터 키가 눌려지면 종료 
while True:
    try:
        temp = int(input())
    except:
        break
    node.append(temp)

#전위 순회에서 왼쪽, 오른쪽, 루트를 분리하여 후위 순회 순서로 재조립하는 과정을 반복하도록 구현된 재귀함수
# node: 전체 노드 리스트 /start: 현재 분할할 범위의 시작 인덱스 /end: 현재 분할할 범위의 끝 인덱스
def divide(node, start, end): 
    #현재 분할할 범위 내에 노드가 없는 경우, 빈 리스트를 반환
    if end == start:
        return []
    #현재 분할할 범위 내에 노드가 하나만 있는 경우, 해당 노드를 담은 리스트를 반환
    if end-start <= 1:
        return [node[start]]

    #현재 분할할 범위의 첫 번째 노드를 루트 노드로 설정
    root = node[start]
	#분할할 범위 내에서 루트 노드보다 큰 값이 처음으로 등장하는 인덱스를 찾기 위한 변수를 초기화
    find_idx = end
    
    for i in range(start+1, end):
        if node[i] > root:
        	#root보다 큰 값이 처음으로 등장하는 인덱스를 기억하기 위한 변수
            find_idx = i
            break
    # 왼쪽 +오른쪽 +루트
    tree = divide(node, start+1, find_idx) + divide(node, find_idx, end) + [node[start]] 
    return tree

tree = divide(node, 0, len(node))
for t in tree:
    print(t)