[백준/C++] 이진 검색 트리

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제를 처음 봤을 때 재귀로 한번에 풀려고 했다.

왜냐하면 이진 트리를 직접 나누기에는 시간이 아슬아슬해 보였기 때문이다.

 

그러나 재귀적으로 풀기가 너무 힘들어 그냥 루트노드에서 원소를 넣으며 이진트리를 만들어 풀었다.

 

즉, 이진트리 만들기 -> 만든 이진트리에서 후위순회하기로 문제를 풀었다.

 

이진트리를 만드는 방법은 아래 그림과 같다.

전위 순회이므로 최상단 루트 노드에서 수를 넣어 이진트리를 만든다.

 

만약 28이 들어오는 경우는 50보다 작으므로 왼쪽 자식이다.

 

이때, 왼쪽 자식의 자리가 비어있지 않으므로 28을 50의 왼쪽 자식인 30과 비교한다.

30보다 작으므로 30의 왼쪽 자식이고 30의 왼쪽 자식의 자리에 24가 있으므로 다시 24와 비교한다.

24와 비교한 후 오른쪽 자식임을 알았고, 오른쪽 자식의 자리가 비어있으므로 28은 24의 오른쪽 자식임을 알 수 있다.

 

45도 마찬가지로 30의 오른쪽 자식이며, 30의 오른쪽 자식의 자리가 비어있으므로 45는 30의 오른쪽 자식이라는 사실을 알 수 있다.

(vector<pair<int,int>>에 왼쪽 자식 오른쪽 자식의 index를 저장해 이진트리를 만들었다.)

 

이렇게 이진트리가 어떻게 구성되어있는지 구했으므로, (왼쪽), (오른쪽), (루트) 순서로 출력하도록 재귀함수를 만들면 된다.

 

 

 

+ 다른 사람의 풀이를 보니 이진트리를 더 빨리 만드는 방법이 있었다...

전위순회는 (왼쪽) (오른쪽) (루트)순으로 탐색을 하므로 이분탐색을 이용하면 루트의 오른쪽 자식들과 왼쪽 자식들을 빠르게 찾을 수 있다.

이를 이용해 이분탐색으로 왼쪽과 오른쪽 자식을 찾아 재귀를 돌리면 직접 이진트리를 그리지 않고 빠르게 풀 수 있다.

 

 

​

[아이디어 정리]

1. 전위순회를 이용해 이진트리를 만든다. (이진트리의 루트노드에 노드를 집어넣어서 특정 노드의 빈 자식의 자리에 도달할 때 까지 이동)
2. 만든 이진트리를 이용해 (왼쪽), (오른쪽), (루트) 순서로 재귀하며 출력한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
using namespace std;

void DFS(vector<pair<int, int>>& childs, vector<int>& v, int nowIdx) { //출력
	if(childs[nowIdx].first != -1) {
		DFS(childs, v, childs[nowIdx].first);
	}
	if (childs[nowIdx].second != -1) {
		DFS(childs, v, childs[nowIdx].second);
	}
	cout << v[nowIdx]<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//vector<int>v=split();
	int a;
	vector<int>v;
	while (cin >> a) {
		if (a == EOF) {
			break;
		}
		v.push_back(a);
	}
	vector<pair<int, int>>childs(v.size(),make_pair(-1,-1));
	int tmp;
	for (int i = 1; i < v.size(); i++) {
		tmp = v[i];
		int nowIdx = 0;
		while (true) {
			if (v[nowIdx] < tmp) { //오른쪽 자식
				if (childs[nowIdx].second == -1) {
					childs[nowIdx].second = i;
					break;
				}
				else
				{
					nowIdx = childs[nowIdx].second;
				}
			}
			else
			{ //왼쪽 자식
				if (childs[nowIdx].first == -1) {
					childs[nowIdx].first = i;
					break;
				}
				else {
					nowIdx = childs[nowIdx].first;
				}
			}
		}
	}
	DFS(childs, v, 0);

	return 0;
}

 

---

괜히 한번에 푸려고 삽질하다 시간이 오래걸린 문제다..

이진트리의 특성을 잘 알고 있었다면 빠르게 풀 수 있었을 텐데...

 

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