[BOJ 2263/C++] 트리의 순회

이진중·2022년 5월 28일

분할정복알고리즘 트리

문제

inOrder와 postOrder로 preOrder를 구하는 문제이다.

풀이

이 문제를 풀면서 2가지 막히는 부분이 있었다.

첫째 : 알고리즘 자체를 모른다. inorder와 postorder를 어덯게해야 preorder가 나오는지 모르겠다.
둘쨰 : 알고리즘을 코드로 옮길수 없다.

첫째, 분할정복 알고리즘

분할정복 알고리즘 : 주어진 문제를 둘 이상의 부분문제로 나눈 뒤 각 문제에 대한 답을 계산하고, 이를 병합해 문제를 해결하는 알고리즘

이진트리를 left, root, right 부분으로 쪼개고, 재귀함수를 활용하여, 쪼갤수 없을때 까지 쪼갠다.
preorder의 순회방식을 이용하여, root->left->right 순서로 값을 출력하면서 순회한다.

쪼개기

post의 마지막 인덱스 값이 root 노드임을 이용
inorder에서 root값의 인덱스(몇번째 순서에 위치해있는지)를 찾는다.
inorder에서 그 root를 기준으로 left와 right로 나눈다.
postorder에서는 inorder에서 구한 left와 right의 크기를 이용하여 left와 right를 나눈다.

둘째, 코드로 옮기기

void getPreOrder(int inStart, int inEnd, int postStart, int postEnd) {

	if (inStart==inEnd || postStart==postEnd)
	{
		cout << inOrder[inStart] << ' ';
		return;
	}

	int root_index = _index[postOrder[postEnd]];
	int leftSize = root_index - inStart;
	int rightSize = inEnd - root_index;

	

	cout << inOrder[root_index]<<' ';
	if (leftSize>=1)
	{
		getPreOrder(inStart,root_index-1,postStart,postStart+leftSize-1);
	}
	if (rightSize>=1)
	{
		getPreOrder(root_index+1,inEnd,postEnd-rightSize,postEnd-1);
	}

	return;
}

inorder의 start와end 인덱스, postorder의 start와 end 인덱스를 각각 인수로 받는다.
start와end인덱스가 같다면 마지막노드이므로, 값을 출력하고 return 한다.
root_index, leftSize, rightSize를 구한다.
root값을 출력한다.
만약 left노드가 존재한다면 재귀함수로 getPreOrder를 다시 호출한다. 이때의 인수는 뒤에서 자세히 다루겠다.
마찬가지로 right노드가 존재한다면 재귀함수 getPreOrder를 다시 호출.

getPreOrder의 인수는 어덯게 구해야할까?

내가 이문제를 풀면서 가장 시간을 많이 쓴 부분이다. 직접 그림으로 그려가면서 감을 잡는 수 밖에없다.

leftNode의 getPreOrder의 인수

inorder의 시작과 끝 인덱스
left노드의 시작은 기존 getPreOrder의 시작과 같은 인덱스이므로, inStart = inStart(기존)
root_index의 앞부분까지가 inorder의 인덱스이므로, inEnd = root_index-1
postorder의 시작과 끝 인덱스
postStart도 마찬가지로 동일 postStart = postStart(기존)
postEnd는 leftSize값과 관련이있다. postStart+leftSize-1이다.

rightNode의 getPreOrder의 인수

inorder의 시작과 끝 인덱스
root뒤부터이므로, inStart = root+1
끝은 동일하므로, inEnd = inEnd(기존)
postorder의 시작과 끝 인덱스
끝지점은 구하기가 쉽다. 기존 끝지점은 root값에 사용되므로, postEnd = postEnd(기존)-1
거기에 사이즈를 빼주면 시작점이 된다. postStart = postEnd(기존)-rightSize

실제 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>

using namespace std;
#define endl "\n"

#define MAX 100000+1
int n;
int inOrder[MAX];
int postOrder[MAX];
int _index[MAX];



void input() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> n;
	
	for (int i = 1; i <= n; i++)
	{
		cin >> inOrder[i];
		_index[inOrder[i]] = i;
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> postOrder[i];
	}
}

void getPreOrder(int inStart, int inEnd, int postStart, int postEnd) {

	if (inStart==inEnd || postStart==postEnd)
	{
		cout << inOrder[inStart] << ' ';
		return;
	}

	int root_index = _index[postOrder[postEnd]];
	int leftSize = root_index - inStart;
	int rightSize = inEnd - root_index;

	

	cout << inOrder[root_index]<<' ';
	if (leftSize>=1)
	{
		getPreOrder(inStart,root_index-1,postStart,postStart+leftSize-1);
	}
	if (rightSize>=1)
	{
		getPreOrder(root_index+1,inEnd,postEnd-rightSize,postEnd-1);
	}

	return;
}


int main()
{
	input();
	getPreOrder(1, n, 1, n);
}