알고스팟 - 쿼드 트리 뒤집기 (QUADTREE) [C++]

 이 문제의 경우 분할 정복을 이용해서 풀었다. 압축된 결과를 보여주고, 이를 상하로 뒤집은 결과를 리턴해야 하는 문제였다. x일 때는 사분면으로 나눠지게 되는데, 왼위, 오위, 왼아, 오아 네가지로 생각했을 때 상하로 뒤집게 된다면 왼아, 오아, 왼위, 오위 순서로 탐색하면 뒤집힌 결과가 나오게 된다. 이를 활용하면 쉽게 풀 수 있는 문제이다.

 

#include <iostream>
#include <string>

using namespace std;

int index;

string parse(string& input) {
	if (input[index] == 'x') {
		string present = "";
		present += input[index++];
		
		string leftUp = parse(input);
		string rightUp = parse(input);
		string leftDown = parse(input);
		string rightDown = parse(input);
		
		return present + leftDown + rightDown + leftUp + rightUp;
	}

	string present = "";
	present += input[index++];
	
	return present;
}

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

	int C;
	cin >> C;

	for (int test = 0; test < C; test++) {
		string input;
		cin >> input;

		index = 0;
		string answer = parse(input);

		cout << answer << '\n';
	}

	return 0;
}