21.3문제: 트리 순회 순서 변경(ID:TRAVERSAL)

문제

트리를 순회하는 알고리즘은 트리의 모든 노드들을 특정 순서에 맞춰 방문하지만, 트리는 배열처럼 1차원적인 구조가 아니기 때문에 단 한 가지의 당연한 순서가 존재하지 않습니다. 때문에 필요에 맞춰 순서를 정의해야 합니다. 이진 트리(binary tree)는 모든 노드에 왼쪽과 오른쪽, 최대 두 개의 자손이 있는 트리를 말하는데, 이진 트리의 순회 순서 중 유명한 세 가지로 전위 순회(preorder traverse), 중위 순회(inorder traverse) 그리고 후위 순회(postorder traverse)가 있습니다. 이들은 모두 왼쪽 서브트리를 오른쪽보다 먼저 방문한다는 점에선 같지만, 트리의 루트를 언제 방문하는지가 서로 다릅니다.
전위 순회는 맨 처음에 트리의 루트를 방문하고, 왼쪽과 오른쪽 서브트리를 순서대로 방문합니다. 중위 순회는 왼쪽과 오른쪽 서브트리 사이에 트리의 루트를 방문하고, 후위 순회는 왼쪽과 오른쪽 서브트리를 모두 방문한 뒤에야 루트를 방문합니다.
다음 그림은 이진 트리의 한 예를 보여 줍니다. 이 트리를 전위 순회하면 모든 노드를 27, 16, 9, 12, 54, 36, 72의 순서대로 방문하게 됩니다. 반면 중위 순회했을 때는 9, 12, 16, 27, 36, 54, 72의 순서로, 후위 순회했을 때는 12, 9, 16, 36, 72, 54, 27의 순서로 방문하게 되지요.

어떤 이진 트리를 전위 순회했을 때 노드들의 방문 순서와, 중위 순회했을 때 노드들의 방문 순서가 주어졌다고 합시다. 이 트리를 후위 순회했을 때 각 노드들을 어떤 순서대로 방문하게 될지 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1≤C≤100)가 주어집니다. 각 테스트 케이스는 세 줄로 구성되며, 첫 줄에는 트리에 포함된 노드의 수 N (1≤N≤100)이 주어집니다. 그 후 두 줄에 각각 트리를 전위 순회했을 때와 중위순회 했을 때의 노드 방문 순서가 N개의 정수로 주어집니다. 각 노드는 1000 이하의 자연수로 번호 매겨져 있으며, 한 트리에서 두 노드의 번호가 같은 일은 없습니다.

출력

각 테스트 케이스마다, 한 줄에 해당 트리의 후위 순회했을 때 노드들의 방문 순서를 출력합니다.

예제 입력

2
7
27 16 9 12 54 36 72
9 12 16 27 36 54 72
6
409 479 10 838 150 441
409 10 479 150 838 441

예제 출력

12 9 16 36 72 54 27
10 150 441 838 479 409

First Thoughts

어디서부터 어떻게 시작해야돼지???

분명 트리의 기본 속성, 순회방법 모두 알고 있고 구현도 할 줄 아는데 전위와 중위 순회에서 후위순회로 바꾸라니.. 이거는 뭐 어떻게 시작해야되는지 감이 오지 않았다. 그래서 책에 아이디어를 참고하여 구현을 해보았다.

My Code

#include <iostream>
#include <vector>
using namespace std;
vector <int> preorder;
vector <int> inorder;
int N;

void postOrder(int pre, int in, int size) {
	int root;
	int i, j;
	if (size < 1)
		return;
	else {
		root = preorder[pre];
		for (i = pre, j = in; i < N; i++, j++) {
			if (root == inorder[j])
				break;
		}
		int lsize = j - in;
		int rsize = (size+in) - (j + 1);
		postOrder(pre + 1, in, lsize);
		postOrder(i + 1, j + 1, rsize);
	}
	cout << root << ' ';
}
int main() {
	int C;
	int i,j,k;
	int num;
	cin >> C;
	for (i = 0; i < C; i++) {
		cin >> N;
		for (j = 0; j < N; j++) {//전위순회
			cin >> num;
			preorder.push_back(num);
		}
		for (k = 0; k < N; k++) {//중위순회
			cin >> num;
			inorder.push_back(num);
		}
		postOrder(0, 0, N);
		cout << "\n";
		preorder.clear();
		inorder.clear();
	}
}

Answer Code

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
vector <int> slice(const vector<int>& v, int a, int b) {
	return vector<int>(v.begin() + a, v.begin() + b);
}
void printPostOrder(const vector<int>& preorder, const vector <int>& inorder){
	const int N = preorder.size();
	if (preorder.empty())
		return;
	const int root = preorder[0];
	const int L = find(inorder.begin(), inorder.end(), root) - inorder.begin();
	const int R = N - 1 - L;
	printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L));
	printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N));
	cout << root <<' ';
 }
int main() {
	int C;
	int N;
	int i, j;
	cin >> C;
	for (i = 0; i < C; i++) {
		cin >> N;
		vector<int> preorder(N);
		vector<int> inorder(N);
		for (j = 0; j < N; j++) {
			cin >> preorder[j];
		}
		for (j = 0; j < N; j++) {
			cin >> inorder[j];
		}
		printPostOrder(preorder, inorder);
		cout << "\n";
	}
}

Difference & Faults

트리의 속성

이 문제에서 가장 어려웠던 점은 첫 아이디어를 구상하는 것이었다. 하지만 책에 코드를 보면 충분히 납득이 갈만하다. 트리의 속성을 잘 이해하고 그것을 응용할 줄 알아야 풀 수 있는 문제인거 같다. 해제 코드를 보고도 어려웠던 점은 포인터를 사용하여 벡터를 따로 추출하는 부분이다. 나는 이 부분을 인덱스를 이용하여 그 사이즈를 직접 구해서 매개변수로 이용하였다. 두 코드 다 장단점이 있겠지만 나에겐 아직 해제 코드의 이해도 어렵다.

Impressions

넓게 보기

재귀함수를 이용할 때 매번 느끼는 것은 문제가 재귀를 통해 어떤 부분이 반복되고 있고 그 부분이 과연 부분 문제로서 작용하는 가 이다. 이번 문제 또한 트리의 속성을 이해하고 어떤 부분이 부분 문제가 되는지를 알았다면 좀 더 쉽게 코드를 작성할 수 있었을 거 같다.

Summary

트리를 본격적으로 시작한다. 자료구조 때도 그렇게 교수님들이 어려울 거니까 정신 똑바로 차리고 제대로 이해하고 가길 바란다고 신신당부하던 트리를 이제는 응용문제들로 접하게 되었다. 개념도 어려운데 문제는 얼마나 어려울까 긴장하며 하나하나 소화하며 갈 수 있길 바란다.