QUADTREE(쿼드트리 뒤집기)

(출처) https://www.algospot.com/judge/problem/read/QUADTREE#

입력으로 주어진 문자열은 X를 기준으로 모두 위 그림과 같은 조각들로 치환이 가능하다. 결국 X의 뒤에 오는 문자열 요소들은 총 4가지 영역으로 구분되어지므로 각각의 영역들을 하나씩 완성시킨 뒤에 마지막에 합쳐주면 되는 문제. 각 영역 TreeN은 'W' or 'B'이거나 새로운 X에 의해서 다시 4개의 영역으로 쪼개지는 경우만 존재한다. 따라서 기저사례는 TreeN이 단순히 'W' or 'B'인 경우이며 TreeN이 X인 경우는 재귀를 통해 다시 4가지 영역으로 나눠져서 작은 부분문제로 분할됨.

입력으로 주어진 문자열 N개를 단순히 앞에서부터 한 개씩 읽어가면서 마지막 요소까지 1번씩만 참조하면 되기 때문에 시간복잡도는 O(N)이 된다. (재귀를 하더라도 지나간 문자열을 다시 볼 필요 없이 마지막에 읽었던 부분부터 다시 공정을 시작하므로 특정 반복은 일어나지 않는다)

분할정복 Part에 해당되는 문제이긴 하지만 분할정복의 개념을 이용해서 시간복잡도를 줄여나간다는 전략이 필요하지는 않았고 그냥 자연스럽게 방법을 찾게 되는 문제였다. 애시당초 쿼드트리 압축자체가 요소를 분할하여 압축해놓은 상태이기때문에 자연스럽게 문제를 푸는 방법도 분할된 요소들을 이용하게 될 뿐이었다. 이 문제를 과연 분할정복 문제라고 볼 수 있을까라는 생각이 들었음.

기억할만한 요소

문자열을 읽어나갈때 나는 재귀함수에 문자열 시작점을 int형 정수로 따로 보내주는 방식을 사용했는데 포인터연산을 이용하면 단순히 문자열 자체만 넘겨줘도 된다는 것을 보았음. 포인터를 이용하면 코드도 깔끔해지고 각 공정마다 시작점을 따로 계산하면서 쓸데없이 머리를 쓸 필요가 없음을 느꼈음.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <time.h>
#include <string>

using namespace std;

string quadtree(char* picture, int start) {
	int next = 0;
	string tree0, tree1, tree2, tree3;

	if (picture[start] == 'x') {
		tree0 = 'x' + quadtree(picture, start + next + 1);
		next += tree0.length(); 
	}
	else {
		tree0 = picture[start + next];
		next++;
	}

	if (picture[start + next] == 'x') {
		tree1 = 'x' + quadtree(picture, start + next + 1);
		next += tree1.length();
	}
	else {
		tree1 = picture[start + next];
		next++;
	}

	if (picture[start + next] == 'x') {
		tree2 = 'x' + quadtree(picture, start + next + 1);
		next += tree2.length();
	}
	else {
		tree2 = picture[start + next];
		next++;
	}

	if (picture[start + next] == 'x') {
		tree3 = 'x' + quadtree(picture, start + next + 1);
		next += tree3.length();
	}
	else {
		tree3 = picture[start + next];
	}


	return tree2 + tree3 + tree0 + tree1;
}

int main() {
	clock_t start, end;
	double result;
	int testcase;
	scanf("%d", &testcase);
	getchar();

	for (int i = 0; i < testcase; i++) {
		char picture [1000];
		scanf("%[^\n]", picture);
		getchar();
		if (picture[0] != 'x') {
			printf("%s\n", picture);
			continue;
		}
		string ret = quadtree(picture, 1);
		ret = 'x' + ret;
		printf("%s\n", ret.c_str());


		//end = clock();
		//result = (double)(end - start);
		//printf("%f", result);
	}

	return 0;
}