QUADTREE

#include <iostream>
#include <string>
#include <string.h>

using namespace std;

const int MAX_BUFFER_SIZE = 1024;

string flip(const char *input, int idx);

int main()
{
	int caseNum = 0;
	char inputBuffer[MAX_BUFFER_SIZE];

	cin >> caseNum;
	cin.ignore();

	for (int cIter = 0; cIter < caseNum; cIter++)
	{
		cin.getline(inputBuffer, MAX_BUFFER_SIZE);

		string result = flip(inputBuffer, 0);

		cout << result << endl;
	}
}

string flip(const char *input, int idx)
{
	if (input[idx] == 'b') return "b";
	else if (input[idx] == 'w') return "w";
	else
	{
		string s[4] = { "", };

		idx++;
		for (int i = 0; i < 4; i++)
		{
			s[i] = flip(input, idx);
			idx += s[i].length();
		}

		return "x" + s[2] + s[3] + s[0] + s[1];
	}
}

- flip() 함수는 기본적으로 3 가지 경우를 다룬다.

- 첫째와 둘째는 각각 픽셀이 "w"(흰색) 일 경우와 "b"(검정) 일 경우다. 이 경우들은 상하 반전할 필요없이 바로 리턴해주면 된다.

- 세번째로 "x" 가 나온다면 그 다음에 오는 문자열이 최소 한개 이상의 쿼드트리를 이루고 있음을 뜻하므로, 상하 반전 작업을 해주어야 한다. 그래서 "x"가 나온 이후부터 (왼쪽 위), (오른쪽 위), (왼쪽 아래), (오른쪽 아래) 의 4가지 경우에 대해 각각 flip() 을 호출한다.

- flip() 은 상하 반전된 문자열을 리턴하는데, 이 리턴한 문자열의 길이를 구해서 다음 번에 탐색할 문자열의 인덱스를 얻는다.

- 50줄도 안되서 해결될줄은 몰랐다..

QuadTreeInput.txt

QuadTreeOutput.txt