[C++] 이진 검색 트리 - 백준#5639번

문제

 

입출력

입력 예시

50
30
24
5
28
45
98
52
60

출력 예시

5
28
24
45
30
60
52
98
50

 

 

풀이

#include <iostream>
#include <vector>
using namespace std;
vector<int> tree;
void ReturnTree(int start, int end)
{
	if (start >= end) return;	// 더 이상 노드가 없을 경우
	if (start == end - 1)		// 노드가 1개 남았을 경우
	{
		cout << tree[start] << endl;
		return;
	}

	int root = tree[start];		// 루트 노드 지정
	int idx = start + 1;
	while (idx < end && tree[idx] < root)
	{
		idx++;
	}
	
	ReturnTree(start+1, idx);	// 루트 기준 왼쪽 서브 트리 재귀
	ReturnTree(idx, end);		// 루트 기준 오른쪽 서브 트리 재귀

	cout << root << endl;
}

int main()
{
	int x;
	while (cin >> x)
	{
		if (x == 0) break;
		else tree.push_back(x);
	}
	ReturnTree(0, tree.size());

	return 0;
}

 

설명

분할 정복 과정과 재귀를 사용하여 문제를 해결한다.

 

문제에도 나와있듯, 이 이진 트리는 항상 만족하는 기준이 있는데

왼쪽 노드는 루트보다 작고, 오른쪽 노드는 루트보다 크다는 것이다.

해서 52 노드와 60 노드의 위치를 보면 60이 52보다 값이 크기에 오른쪽에 위치한 것을 볼 수 있다.

 

입력된 숫자들은 전위 순회가 완료된 순서로 값들이 주어진다고 하였다.

전위 순회란, '루트 - 왼쪽 - 오른쪽' 의 순서대로 탐색하는 과정이기에 후위 순회는 그 반대 개념인 '왼쪽 - 오른쪽 - 루트' 의 과정으로 진행한다.

사실 처음 이 개념을 접했을 때 '전위의 반대면 '오른쪽 - 왼쪽 - 루트' 아닌가?' 하는 생각이 들었지만, 후위 순회가 단순히 전위 순회의 과정을 그대로 뒤집은 것이 아니라, 루트 노드를 먼저/자식 노드를 먼저 의 개념을 뒤집는 것이고 표준 후위 또한 '왼쪽 - 오른쪽 - 루트' 의 순서를 보여준다.

 

다시 코드로 돌아가서, Main 에서는 입력하는 값을 차례대로 Tree Vector 에 저장한다. 이때 입력되는 값 중 0이 입력되면 루프를 종료하도록 하였다.

이후 ReturnTree에 진입하는데, 매개변수로는 첫 시작 노드와 마지막 노드(tree.size()) 를 지정해준다.

 

ReturnTree에서는 매개변수를 start 와 end로 받는다. 이 두 변수는 현재 메서드 내에서 일정 범위 내의 트리를 순회할텐데, 그 범위의 시작과 끝을 알리는 개념이다.

 

먼저 두 조건문을 설정한다.

만약 탐색할 노드가 남아있지 않다면, start >= end 라면 메서드를 종료한다.

그리고 만약 탐색할 노드가 하나만 남았다면, 이 노드만 탐색 후 종료될 것이기에 해당 노드의 값을 출력하고 메서드를 종료한다.

 

이 두 조건문을 넘었다면 현재 메서드가 탐색하고 있는 트리의 범위는 적어도 두개 이상의 노드를 가지고 있다.

따라서 왼쪽 서브 트리와 오른쪽 서브 트리를 나누기 위해 루트 노드를 지정해줘야 하는데, 루트는 항상 현재 배열의 가장 첫번째에 위치하기에 tree[start] 로 지정해준다.

또한 주어진 배열에는 루트를 기준으로 왼쪽은 더 작은 값, 오른쪽은 더 큰 값이 위치한다.

이 분기점을 찾기 위해 while 문을 통해 이 조건에 만족하는 요소를 찾고, 그 요소의 인덱스를 idx 로 저장한다.

 

여기서 원활한 이해를 위해 예시 상황을 들어보는데, 첫 ReturnTree에 진입한 상황이라고 가정해보자.

start 는 0, end는 9로 주어진다. 첫 두 조건문은 모두 만족하지 않기에 넘어가고, root 는 tree[start] 인 50으로 저장된다.

idx는 start + 1 인 1로 시작되어 while문을 거치고 나면 6으로 저장된다.

root = 50
idx = 6

 

이 idx 가 왼쪽 트리와 오른쪽 트리를 나눌 기준이 된다.

 

해서 여기서 분할 정복과 재귀가 동시에 사용된다.

트리의 왼쪽/오른쪽으로 나누며 탐색이 진행되어야 하기 때문에 분할을, 같은 코드를 재활용하기 위해 재귀를 사용한다.

 

ReturnTree(start+1, idx) 는 왼쪽 서브 트리를 담당한다.

start 는 root 로 지정되어 있기 때문에 root 의 다음인 start + 1 부터 기준점인 idx 까지 범위를 잡는다.

ReturnTree(idx, end) 는 오른쪽 서브 트리를 담당한다.

기준점인 idx 와 배열 범위의 마지막인 end 까지 범위를 잡는다.

 

여기서 혼동이 있었던 부분은 idx 를 양쪽 모두에서 사용한다는 점이었다.

왼쪽 트리에서도 idx까지, 오른쪽 트리에서는 idx부터 범위가 시작된다면 idx에 위치한 값은 두번 출력되는 것이 아닌가? 라고 오해했는데, 이 매개변수를 통한 범위는 정확하게는 start <= 범위 < idx 로 측정되어 end 에 위치한 값은 포함되지 않는다.

start 가 2, end가 5 라면 순회는 2, 3, 4 내에서만 이루어지는 것이다.

 

이렇게 재귀 호출을 통해 지속적으로 왼쪽 서브 트리와 오른쪽 서브 트리를 나누다보면 노드가 하나만 남아서 출력이 되는 시기가 온다.

이때 출력 순서는 앞서 말한 후위 순회의 개념대로 '왼쪽 - 오른쪽 - 루트' 의 순서대로 진행된다.