[백준알고리즘] 2263번: 트리의 순회-C++

2263번: 트리의 순회 (acmicpc.net)

2263번: 트리의 순회

정답률과 골드 문제여서 쉽게 봤다가 시간을 많이 잡아먹었다. 그런데 접근법 자체 때문인 건 아니고, 메모리 초과가 발생했어서 코드를 약간 수정하는 게 너무 귀찮아서 오래 걸렸다.

list를 여러번 생성하면서 재귀적으로 문제를 풀었는데, 10만 개가 한 줄로 이어진 경우에는 스택이 모자란 것으로 보인다. 그래서 list를 매번 생성해서 넘겨주는 것이 아닌, 인덱스로 접근하는 방법을 선택했다. 그러다 보니, list를 vector로 변경해주었다. 이 과정이 너무 귀찮았다.

접근법 자체는 간단하게 풀렸다.

---

문제 풀이

In-order와 Post-order가 주어졌을 때, Pre-order로 출력을 해주면 된다. 각 순회법은 아래와 같은 순서로 트리를 탐색한다.

• Pre-order : 루트 노드 - 왼쪽 자식 - 오른쪽 자식
• In-order :왼쪽 자식 - 로트 노드 - 오른쪽 자식
• Post-order : 왼쪽 자식 - 오른쪽 자식 - 로트 노드 

즉, 루트 노드의 위치에 따라 Pre / In / Post 가 결정된다.

 

문제에서는 In-order와 Post-order가 주어진다. 사실 왼쪽 / 오른쪽 자식은 모두 서브트리를 의미한다. 그리고, 루트 노드는 단일 노드다.

따라서, In-order에서의 왼쪽 자식과 오른쪽 자식, Post-order에서의 왼쪽 자식과 오른쪽 자식을 구분하는 방법은 '루트 노드'가 누구인지 알면 되는 것이다.

 

순회법에 대해 보면, Post-order의 가장 끝의 노드는 항상 로트 노드이다. In-order와 Post-order의 루트 노드의 값은 같은 값이기 때문에, 루트 노드 덕분에 In-order의 왼쪽 자식과 오른쪽 자식의 범위를 알 수 있다.

또한, In-order와 Post-order 모두 같은 트리를 대상으로 하기 때문에, 왼쪽 자식 트리의 크기(노드의 개수)와 오른쪽 자식 트리의 크기(노드의 개수)는 동일하다. 이를 이용해 Post-order에서도 왼쪽 자식과 오른쪽 자식을 구할 수 있다.

 

이렇게 왼쪽 자식 범위와 오른쪽 자식 범위를 알게 되면, 이들을 이용해 Pre-order 방식으로 변경하면 된다.

나머지는 자식(서브 트리)마다 모두 In-order와 Post-order를 Pre-order로 재귀적으로 변경해나가면 된다.

 

오늘은 아래의 코드를 좀 더 정리할 수 있었을 텐데, 그거는 하지를 못했다. 위의 아이디어가 쉽기 때문에 그냥 놔둔다.

#include <cstdio>
#include <vector>

std::vector<unsigned int> vecInOrder;
std::vector<unsigned int> vecPostOrder;

const unsigned int inputNodeSize();
std::vector<unsigned int> inputTree(const unsigned int uiSize);
std::vector<unsigned int> getPreOrder(const unsigned int uiInOrderLeftIndex, const unsigned int uiInOrderRightIndex, const unsigned int uiPostOrderLeftIndex, const unsigned int uiPostOrderRightIndex);
void printVector(const std::vector<unsigned int> &vec);

int main(void) {
	const unsigned int uiSize = inputNodeSize();
	vecInOrder = inputTree(uiSize);
	vecPostOrder = inputTree(uiSize);
	std::vector<unsigned int> vecPreOrder = getPreOrder(0, uiSize, 0, uiSize);
	printVector(vecPreOrder);
	return 0;
}

const unsigned int inputNodeSize() {
	unsigned int uiSize = 0;
	scanf("%u", &uiSize);
	return uiSize;
}

std::vector<unsigned int> inputTree(const unsigned int uiSize) {
	std::vector<unsigned int> vecTree;
	for ( unsigned int uiCount = 0; uiCount < uiSize; ++uiCount ) {
		unsigned int uiNode = 0;
		scanf("%u", &uiNode);
		vecTree.push_back(uiNode);
	}
	return vecTree;
}

std::vector<unsigned int> getPreOrder(const unsigned int uiInOrderLeftIndex, const unsigned int uiInOrderRightIndex, const unsigned int uiPostOrderLeftIndex, const unsigned int uiPostOrderRightIndex) {
	if ( uiInOrderLeftIndex + 1 == uiInOrderRightIndex ) {
		return std::vector<unsigned int>(1, vecInOrder[uiInOrderLeftIndex]);
	}
	if ( uiInOrderLeftIndex >= uiInOrderRightIndex ) {
		return std::vector<unsigned int>();
	}

	const unsigned int uiRootNode = vecPostOrder[uiPostOrderRightIndex - 1];

	unsigned int uiInOrderLeftChildLeftIndex = 0;
	unsigned int uiInOrderLeftChildRightIndex = 0;
	unsigned int uiInOrderRightChildLeftIndex = 0;
	unsigned int uiInOrderRightChildRightIndex = 0;
	unsigned int uiPostOrderLeftChildLeftIndex = 0;
	unsigned int uiPostOrderLeftChildRightIndex = 0;
	unsigned int uiPostOrderRightChildLeftIndex = 0;
	unsigned int uiPostOrderRightChildRightIndex = 0;

	for ( unsigned int uiInOrderIndex = uiInOrderLeftIndex, uiPostOrderIndex = uiPostOrderLeftIndex;
		 uiInOrderIndex < uiInOrderRightIndex && uiPostOrderIndex < uiPostOrderRightIndex;
		 ++uiInOrderIndex, ++uiPostOrderIndex ) {
		if ( vecInOrder[uiInOrderIndex] == uiRootNode ) {
			uiInOrderLeftChildLeftIndex = uiInOrderLeftIndex;
			uiPostOrderLeftChildLeftIndex = uiPostOrderLeftIndex;

			uiInOrderLeftChildRightIndex = uiInOrderIndex;
			uiPostOrderLeftChildRightIndex = uiPostOrderIndex;

			uiInOrderRightChildLeftIndex = uiInOrderIndex + 1;
			uiPostOrderRightChildLeftIndex = uiPostOrderIndex;

			uiInOrderRightChildRightIndex = uiInOrderRightIndex;
			uiPostOrderRightChildRightIndex = uiPostOrderRightIndex - 1;

			break;
		}
	}

	std::vector<unsigned int> vecPreOrder;
	vecPreOrder.push_back(uiRootNode);
	std::vector<unsigned int> vecLeftChild = getPreOrder(uiInOrderLeftChildLeftIndex, uiInOrderLeftChildRightIndex, uiPostOrderLeftChildLeftIndex, uiPostOrderLeftChildRightIndex);
	vecPreOrder.insert(vecPreOrder.end(), vecLeftChild.begin(), vecLeftChild.end());
	std::vector<unsigned int> vecRightChild = getPreOrder(uiInOrderRightChildLeftIndex, uiInOrderRightChildRightIndex, uiPostOrderRightChildLeftIndex, uiPostOrderRightChildRightIndex);
	vecPreOrder.insert(vecPreOrder.end(), vecRightChild.begin(), vecRightChild.end());

	return vecPreOrder;
}

void printVector(const std::vector<unsigned int> &vec) {
	for ( const unsigned int uiValue : vec ) {
		printf("%u ", uiValue);
	}
}