[C/C++] 백준 2263번 - 트리의 순회

 

<코드>

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int n;
int inorder[100001]; // 중위
int postorder[100001]; // 후위
int memo[100001];

void preorder(int in_s, int in_e, int post_s, int post_e)
{
	if (in_s > in_e || post_s > post_e) return;
	int root = postorder[post_e];
	int idx = memo[root]; // 인오더에서 루트의 인덱스
	int L = idx - in_s;
	cout << root << " ";

	preorder(in_s, idx - 1, post_s, post_s + L - 1);
	preorder(idx + 1, in_e, post_s + L, post_e - 1);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> inorder[i];

	for (int i = 1; i <= n; i++)
		cin >> postorder[i];

	// 인오더에서 해당 값이 어디에 있는지 인덱스 기록
	for (int i = 1; i <= n; i++)
		memo[inorder[i]] = i; 

	preorder(1, n, 1, n);

}

 

<7달 뒤 다시 풀어본 코드>

#include <iostream>
using namespace std;

int n;
int in_Order[100001];
int post_Order[100001];

// 중위순회배열(s1~e1) / L / Root / R
// 후위순회배열(s2~e2) / L / R / Root
void DFS(int s1, int e1, int s2, int e2) { 

	if (s1 > e1 || s2 > e2) return;
	int Root = post_Order[e2];

	int idx = -1;
	for (int i = s1; i <= e1; i++)
	{
		if (in_Order[i] == Root) {
			idx = i;
			break;
		}
	}
	int L_cnt = idx - s1; // Left 개수

	// Root
	cout << Root << " ";
	// L
	DFS(s1, idx - 1, s2, s2 + L_cnt - 1);
	// R
	DFS(idx + 1, e1, s2 + L_cnt, e2 - 1);
}

int main() {
    
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> in_Order[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> post_Order[i];
	}

	DFS(1, n, 1, n);
}

 

풀이 방법

 

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

 

주된 알고리즘을 살펴보자면 

Void DFS(중위순회 범위, 후위순회 범위){

	루트출력();
	DFS(중위순회의 L부분 범위, 후위순회의 L부분 범위);
    	DFS(중위순회의 R부분 범위, 후위순회의 R부분 범위);

}

후위 순회의 가장 끝 부분은 루트이며
이 루트는 전위 순회의 가장 앞부분인 루트라고 알 수 있습니다. 

즉, 후위 순회를 안다면 루트의 값 알아낼 수 있고
중위 순회에서 그 루트 값 위치에 따라 L부분과 R부분으로 쪼갤 수 있습니다.

그리고 그 쪼갠 부분들로 후위 순회를 L부분과 R부분으로 쪼갤 수 있고 
따라서 재귀적으로 전회 순회를 구현할 수 있게 됩니다.

 

예를 들어보겠습니다.

중위 순회 결과 : DBAECFG
후위 순회 결과 : DBEGFCA

이때 루트 값은 후위 순회의 마지막 값인 'A'가 됩니다.
(후위 순회의 구조가 L/R/Root 이기 때문!)

그리고 중위 순회에서 루트 값인 'A'를 기준으로 Left (DB)와 Right (ECFG)로 나눠지게 됩니다.
(중위 순회의 구조가 L/Root/R 이기 때문!)

위치	Left	Root	Right
중위 순회	DB	A	ECFG

이 정보를 통해 후위 순회도 L과 R으로 나눌 수 있습니다.
(Because 중위 순회 L부분 개수 == 후위 순회 L부분 개수, 중위 순회 R부분 개수 == 후위 순회 R부분 개수 이기 때문!)

위치	Left	Right	Root
후위 순회	DB	EGFC	A

 

그렇다면 위의 과정을 코드로 나타낸다면 아래와 같이 될 것입니다.

Void DFS(DBAECFG, DBEGFCA){

	루트출력(A); // Root
	DFS(DB, DB); // Left
    	DFS(ECFG, EGFC); // Right

}

 

따라서 아래와 같은 DFS 코드가 나오게 됩니다.

void DFS(int s1, int e1, int s2, int e2) { 

	if (s1 > e1 || s2 > e2) return;
	int Root = post_Order[e2];

	int idx = -1;
	for (int i = s1; i <= e1; i++)
	{
		if (in_Order[i] == Root) {
			idx = i;
			break;
		}
	}
	int L_cnt = idx - s1; // Left 개수

	// Root
	cout << Root << " ";
	// L
	DFS(s1, idx - 1, s2, s2 + L_cnt - 1);
	// R
	DFS(idx + 1, e1, s2 + L_cnt, e2 - 1);
}

s1, e1은 중위 순회의 범위, s2, e2은 후위 순회의 범위입니다. 
이때 (s1 > e1 || s2 > e2) 이면 오류가 발생하므로 return;으로 함수를 종료시켜줍니다.

루트 값은 아까 말씀드렸다시피 후위 순회의 끝부분 post_Order[e2] 이고,
이 값을 통해서 중위 순회의 루트 idx를 구하게 됩니다.

그 idx를 통해서 중위 순회를 L과 R로 나눌 수 있게 되며, L부분의 개수(L_cnt)를 알아낼 수 있습니다.
그리고 그 L_cnt를 통해서 후위 순회를 L과 R로 나눌 수 있으며 
중위와 후위 순회 L부분, 중위와 후위 순회 R부분 각각 재귀를 할 수 있습니다.  

 

<그림으로 과정 설명>

 

 

 

 

 

www.acmicpc.net/problem/2263

2263번: 트리의 순회