[C/C++] 백준 2263번

문제출처: https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

[ 문제 ]

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

[ 입력 ]

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

[ 출력 ]

첫째 줄에 프리오더를 출력한다.

[ 풀이 ]

※ 본 문제의 풀이는 트리의 순회 방식(전위 순회, 중위 순회, 후위 순회)을 이해하고 있음을 전제로 한다.

 

중위 순회와 후위 순회가 주어졌을 때 전위 순회를 구하기 위해서는 '분할 정복 알고리즘'을 활용한다. 다음은 기본적인 해결 순서이다.

 

- 다음과 같은 후위 순회, 중위 순회 순서가 주어졌다고 가정하자.

 

[후위 순회] 2 8 7 1 10 9 4 3

[중위 순회] 2 1 7 8 3 4 10 9

 

(1) 우선, 후위 순회의 가장 마지막 값은 항상 루트 노드이다.

(2) 중위 순회에서 (1)에서 찾은 루트 노드 기준 왼쪽 값들은 해당 트리의 왼쪽 sub tree이고, 오른쪽 값들은 오른쪽 sub tree이다.

그러므로 다음의 결과가 나타난다.

 

(1), (2)를 왼쪽 sub tree와 오른쪽 sub tree에 반복적으로 수행하여 1개의 원소가 나타날 때까지 분할한다면 

위와 같은 완성된 트리를 만들어 낼 수 있고, 전위 순회 순서를 구할 수 있다.

 

문제를 해결하기 위해 트리를 구현할 필요는 없고, 전위 순회는 트리 or 각 서브 트리의 루트 노드를 가장 먼저 방문하는 순회 방식이기 때문에 각 분할이 이루어질 때마다 각 sub tree의 후위 순회에서 루트 노드를 구해 출력한다면 전위 순회 순서를 구할 수 있다.

 

void getPre(int inBegin, int inEnd, int postBegin, int postEnd)
{
    if(inBegin > inEnd || postBegin > postEnd)
    {
        return;
    }
    // 후위순회 가장 마지막 노드로 root 노드 구하기
    int r = arr_post[postEnd];
    int k;
    
    // 전위순회에서 root 노드의 index 구하기
    for(int i = inBegin; i <= inEnd; i++)
    {
        if(arr_in[i] == r)
        {
            k = i;
        }
    }
    
    int leftsize = k - inBegin;
    
    // 분할 전 root 노드 출력
    printf("%d ", r);
    
    // 왼쪽 sub tree
    getPre(inBegin, k-1, postBegin, postBegin + leftsize - 1);
    // 오른쪽 sub tree
    getPre(k+1, inEnd, postBegin + leftsize, postEnd-1);
}

[중위 순회 순서]

- inBegin ~ k-1 : 시작점부터 루트 노드의 index인 k의 직전까지가 왼쪽 sub tree의 원소들이므로.

- k+1 ~ inEnd: 루트 노드의 index인 k의 직후부터 끝점까지가 오른쪽 sub tree의 원소들이므로.

 

[후위 순회 순서]

- postBegin ~ postBegin + leftsize - 1 : 시작점부터 왼쪽 subtree의 크기-1(index 기준)까지가 왼쪽 sub tree의 원소들이므로.

위의 예시에서 첫 번째 왼쪽 sub tree의 원소는 root 노드인 3의 왼쪽 (2 1 7 8)이므로 size는 4이다. 그러므로 후위 순회 순서에서도 시작점을 기준으로 원소 개수가 4가 되는 index가 왼쪽 sub tree의 원소 범위이다.

- postBegin + leftsize ~ postEnd-1 : 왼쪽 sub tree의 끝점 + 1이 후위 순회 순서에서 오른쪽 sub tree 원소들의 시작점이므로 postBegin + leftsize가 시작점이 되고, 해당 sub tree의 root를 나타내는 postEnd는 분할될수록 1씩 줄어야 하므로 postEnd-1이 끝점이다.

 

#include <iostream>

using namespace std;

int arr_in[100001];
int arr_post[100001];
int n;

void getPre(int inBegin, int inEnd, int postBegin, int postEnd)
{
	if(inBegin > inEnd || postBegin > postEnd)
	{
		return;
	}
	
	int r = arr_post[postEnd];
	int k;
	for(int i = inBegin; i <= inEnd; i++)
	{
		if(arr_in[i] == r)
		{
			k = i;
		}
	}
	
	int leftsize = k - inBegin;
	
	printf("%d ", r);
	
	getPre(inBegin, k-1, postBegin, postBegin + leftsize - 1);
	getPre(k+1, inEnd, postBegin + leftsize, postEnd-1);
}

int main(void)
{
	int i, j;
	scanf("%d", &n);
	
	for(i = 0; i < n; i++)
	{
		scanf("%d", &arr_in[i]);
	}
	
	for(j = 0; j < n; j++)
	{
		scanf("%d", &arr_post[j]);
	}
	
	getPre(0, n-1, 0, n-1);
	
	return 0;
}

 

[ 추가 ]

이 외에도

(1) 중위 순회 - 전위 순회 

(2) 중위 순회 - 레벨 순회

로도 기존의 트리를 구할 수 있다. 즉, 서로 다른 순회의 조합으로 유일한 이진 트리를 정의할 수 있음을 의미한다.

단, 이 외의 다른 조합으로는 이진 트리를 유일하게 정의할 수 없다.

 

[ 소감 ]

사실 서로 다른 순회의 조합으로 기존의 트리를 구하는 것은 학기 중 자료구조 수업에서 배운 내용이라 구현이 쉬울 줄 알았지만, 내용을 알고 있다고 해서 무조건 구현해낼 수 있는 것은 아님을 깨달을 수 있었다. 

분할 정복 알고리즘까지 접근은 했으나 트리를 직접 구현한 후 전위 순회를 출력해야 하는 것인지, 트리를 직접 구현하지 않고도 구할 수 있는 것인지 / 분할의 '범위'를 어떻게 나누어야 할 지에서 가장 많은 시간을 할애했다.

 

분할 정복 알고리즘에 대해서도 복습할 수 있었던 좋은 문제였다!