백준 4256(트리)

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

4256번: 트리

 

이진 트리의 전위, 중위, 후위 순회에 대한 문제다. 

 

일단 전위 순회의 결과와 중위 순회의 결과로 후위 순회를 구할 수 있도록 문제가 주어진다고 했다. 

 

그러면 어떻게 전위 순회와 중위 순회로 후위 순회를 구할 수 있을까. 

 

전위는 방문이 먼저인 VLR구조이고, 중위는 LVR구조이다. 

 

방문을 먼저한다는게 후위 순회를 위해서 이진트리구조를 알 수 있는 핵심이라고 생각한다. 

 

무조건 root부터 순회를 시작하는 구조에서 방문을 먼저한다 -> 가장 먼저 출력되는 값 = root

 

그래서 문제해결방법은 subtree안의 subtree를 계속해서 구하는 방식으로 진행된다.

 

예시에서

 

a = 3 2 1 4

b = 2 3 4 1

 

이 각각 순회의 결과라고 한다면 3은 무조건 root이다. 

그러고 중위 순회의 구조를 조사해보면 LVR, 방문이 중간이다. 

 

여기서는 dfs의 작동원리를 이해하고 있으면 쉽게 이해할 수 있지만 그렇지 않으면 어려울 수도 있다.

 

방문이 중간이라는 소리는 모든 L-subtree를 조사하고 나서 방문 후 R-subtree를 조사한다는 소리이다. 

그러므로 중위 순회에서 3의 위치를 기준으로 왼쪽은 L-subtree, 오른쪽은 R-subtree이다. 

 

따라서 문제는 재귀적으로 진행된다. 

 

a에서 root를 구함

root = 3 

왼쪽에 노드 2가 존재.

오른쪽에 4, 1이 존재.

 

subtree로 진행 

a에서 root를 구함

root = 2

왼쪽에 존재 x

오른쪽에 존재 x

 

다시 진행 

a에서 root를 구함

root = 1

왼쪽에 4

오른쪽에 존재 x

 

이렇게 재귀적으로 진행된다 .

 

그래서 우리가 해야될 일은 조사 범위를 함수의 매개변수로 넣어서 subtree의 조사범위를 제한시켜준다. 

 

	solve(l, tmp-1, index+1); 왼쪽 서브트리
	solve(tmp+1, r, index+tmp-l+1); 오른쪽 서브트리

 index의 값을 설정해주는게 꽤 까다로웠는데 그냥 뭐를 구하려고 하는지만 잘 생각해보면 구할 수 있는 것 같다.

 

이제 언제 후위 연산을 위해서 값을 출력시켜야 할 지 생각해보자

 

후위 연산은 LRV이다. 따라서 l_subtree와 r_subtree 뒤에 원하는 값을 출력한다. 

 

#include<iostream>
using namespace std;
#define MAX 1001

int T, n;
int a[MAX];
int b[MAX];

void solve(int l, int r,  int index) {
	if (l > r) return;
	int tmp = b[a[index]];
	solve(l, tmp-1, index+1);
	solve(tmp+1, r, index+tmp-l+1);
	cout << a[index] << " ";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> n;
		for (int j = 0; j < n; j++) {
			cin >> a[j];
		}
		for (int j = 0; j < n; j++) {
			int tmp;
			cin >> tmp;
			b[tmp] = j;
		}
		solve(0, n - 1, 0);
		cout << "\n";
	}

	
}