백준 2263번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
5초	128MB	골드 1

사진을 클릭하면 문제로 이동합니다.

---

풀이

 트리의 순회결과를 보고, 원래의 트리를 원복하는 문제이다. 예전부터 정말 악연이 깊고, 관심이 있던 알고리즘이다.

 

 사실 이 문제 자체는 학교시험에서 풀어보았다. 예전의 나는 1학년을 마치고 나서 자료구조와 알고리즘을 재밌게 공부하던 만큼, 2학년에 올라가 자료구조 전공 과목에서 중간고사와 과제를 만점에 가깝게 받으며 예습에 대한 뿌듯함을 느끼고 있었다. 하지만, 기말고사 범위에 트리가 들어왔고, 역시 나름 공부했다. 개념들은 어렵지 않았으니 배우고 이해하는건 쉬웠다. 하지만, 트리파트에서 이 문제가 나왔다. 정확히는 트리의 두가지 순회 결과를 보고 이진트리를 원복하여 그리라는 문제였다. 그런 류의 문제를 처음 접했었고, 이런 류의 문제가 5문제정도 나왔던 것으로 기억한다. 덕분에 시간을 주구장창 뺏겨 점수가 떨어졌던 기억이 있다.

 

 이를 잊고 살다가, 백준에서 이러한 문제를 몇번 읽어봤고, 이번에 마침내 풀어냈다. 잡설이 길었으니, 바로 풀이를 설명해보자. 해당 문제는 중위 순회 결과와 후위 순회 결과를 보고 트리를 원복하여 전위 순회를 하는 문제이다. 후위순회의 경우, 순회 결과의 마지막 원소가 전체 트리의 루트 노드임을 알 수 있다. 후위순회의 정의 때문이다. 후위순회 결과의 맨 마지막 원소부터 앞으로 갈수록 자신의 오른쪽 서브트리의 루트임을 알 수 있다. 전위순회는 반대일 것이다. 중위 순회결과에서 루트 노드의 좌우로, 본인의 서브트리가 존재한다. 후위순회 결과에서 계속 루트노드를 찾고, 해당 결과에 맞게 중위순회 결과에서 해당 루트의 위치를 찾고, 좌우 서브트리로 재귀하며 트리를 계속해서 원복한다.

 

트리의 원복이 끝났다면, 전위 순회 코드를 간단하게 작성하여 돌려주면 된다.

코드

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> post, in;
vector<pair<int,int>> tree;

void input() {
	cin >> n;
	post.resize(n), in.resize(n), tree.resize(n + 1);
	for(int& x : in) cin >> x;
	for(int& x : post) cin >> x;
}

void preorder(int r) {
	if (!r) return;

	auto& [cl, cr] = tree[r];

	cout << r << ' ';
	preorder(cl);
	preorder(cr);
}

int build_tree_post_in(int l, int r) {
	if (l >= r) return 0;

	int root = *post.rbegin(); post.pop_back();
	int idx = distance(in.begin(), find(in.begin() + l, in.begin() + r, root));
	if (idx == r) return 0;
	
	auto& [cl, cr] = tree[root];
	cr = build_tree_post_in(idx + 1, r);
	cl = build_tree_post_in(l, idx);
	return root;
}

void sol() {
	int root = post[n - 1];
	build_tree_post_in(0, n);
	preorder(root);
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol();
}