[BOJ/백준 4256/C++] 트리

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

4256번: 트리

 

[문제 요약]

- 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. 노드 n개로 이루어진 이진 트리를 BT라고 하자. BT의 노드는 1부터 n까지 유일한 번호가 매겨져 있다.

- 아래 그림에 나와있는 BT의 루트는 3번 노드이다. 1번 노드는 오른쪽 자식만 가지고 있고, 4와 7은 왼쪽 자식만 가지고 있다. 3과 6은 왼쪽과 오른쪽 자식을 모두 가지고 있다. 나머지 노드는 모두 자식이 없으며, 이러한 노드는 리프 노드라고 부른다.

- BT를 전위 순회, 중위 순회한 결과가 주어진다. 즉, 위의 함수 중 preorder(root node of BT)와 inorder(root node of BT)를 호출해서 만든 리스트가 주어진다. 두 순회한 결과를 가지고 다시 BT를 만들 수 있다.

- BT의 전위, 중위 순회한 결과가 주어졌을 때, 후위 순회했을 때의 결과를 구하는 프로그램을 작성하시오.

 

[문제 조건]

- 첫째 줄에 테스트 케이스의 개수 T가 주어진다.

- 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000)

- BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다.

- 다음 줄에는 BT를 전위 순회한 결과, 그 다음 줄에는 중위 순회한 결과가 주어진다. 항상 두 순회 결과로 유일한 이진 트리가 만들어지는 경우만 입력으로 주어진다.

 

[문제 풀이]

전위 순회의 경우 맨 앞의 경우는 루트 노드의 번호가 오고 그 다음 부터는 각 서브트리의 루트 노드 번호가 먼저 오게 된다. (왼쪽 서브트리 부터)

따라서 전위 순회의 결과를 처음부터 확인하면서 중위 순회의 결과를 두개로 나누어 확인하면서 후위 순회의 방식대로 출력해주면 간단하게 풀리는 문제다.

 

간단하게 예를들어 설명해보자면, 위의 예제의 경우

전위 : 3,6,5,4,8,7,1,2

중위 : 5,6,8,4,3,1,2,7

 

전위의 첫번째 원소가 3이니까 중위의 결과를 (5,6,8,4) 3 (1,2,7) 과 같이 나누어 준다.

다음 원소는 6임으로 ((5) 6 (8,4)) 3 (1,2,7) 6을 기준으로 2개로 나누어주는 방식이다. 이때 출력은 후위 순회의 방식과 같은 방식으로 출력해주면 정답이 된다.

 

[소스 코드]

#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <vector>
#include <map>

#define INF 987654321
#define pii pair<int,int>

using namespace std;

int T, N;

void divide(int *pos, int s, int e, vector<int> &pre, vector<int> &input)
{
	if (s >= e)
	{
		*pos = *pos + 1;
		cout << input[s] << " ";
		return;
	}
	int mid;
	*pos = *pos + 1;
	int cur = *pos;
	for (int i = s; i <= e; i++)
	{
		if (input[i] == pre[*pos]) { mid = i; break; }
	}

	if(s <= mid -1) divide(pos, s, mid-1, pre, input);
	if(mid+1 <= e) divide(pos, mid + 1, e, pre, input);
	cout << pre[cur] << " ";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> T;
	while (T--)
	{
		cin >> N;
		vector<int> pre(N, 0); vector<int> in(N, 0);
		for (int i = 0; i < N; i++) cin >> pre[i];
		for (int i = 0; i < N; i++) cin >> in[i];

		int pos = -1;
		divide(&pos, 0, N-1, pre, in);
		cout << "\n";
	}
}

 

굳