[알고스팟] 쿼드트리 뒤집기

https://www.algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

---

해당 문제의 풀이에는 분할 정복을 사용합니다. 분할 정복이란 문제를 더 작은 부분문제들로 나누고, 부분문제들의 결과를 적절히 조합하여 전체 정답을 도출하는 과정입니다. 흔히 알려진 바로는 분할(divide) - 병합(merge)의 단계를 거쳐 푼다고 합니다.

 쿼드트리 자체가 재귀적으로 정의되어 있기 때문에 재귀 호출을 사용하여 압축 혹은 압축 해제하는 것이 효과적입니다. 따라서 다음과 같이 해답을 작성해볼 수 있습니다.

<Python3 소스 코드>

def reverse_tree(idx:int):
    if tree[idx] == 'w': return 'w', idx + 1
    elif tree[idx] == 'b': return 'b', idx + 1
    
    new_idx = idx + 1
    quad = [None for _ in range(4)]
    for i in range(4):
        quad[i], new_idx = reverse_tree(new_idx)
    return 'x' + quad[2] + quad[3] + quad[0] + quad[1], new_idx
    
            
for _ in range(int(sys.stdin.readline())):
    tree = sys.stdin.readline()    
    print(reverse_tree(0)[0])

문제의 해결에서 어려운 점은 재귀가 어디서 발생할 지 모르고, 따라서 내가 현재 탐색해야할 문자의 인덱스를 얻기가 어렵다는 점입니다. 위 코드에서는 다음 인덱스를 재귀적으로 반환하여 탐색을 진행하고 있지만, 경우에 따라 상위 컨텍스트에서 변수를 관리해도 무방할 것 같습니다. 

<C++ 소스 코드>

#include <iostream>
#include <cstdio>
using namespace std;


string reverse(string::iterator& it)
{
	char head = *it;
	++it;
	if (head == 'b' || head == 'w')
		return string(1, head);
	string upperLeft = reverse(it);
	string upperRight = reverse(it);
	string lowerLeft = reverse(it);
	string lowerRight = reverse(it);

	return string("x") + lowerLeft + lowerRight + upperLeft + upperRight;
}

int main(void)
{	
	int num_testcase;
	scanf("%d", &num_testcase);
	for (int i = 0; i < num_testcase; i++)
	{
		char input[1000];
		scanf("%s", input);
		string inputString = input;
		string::iterator iter = inputString.begin();
		string ret = reverse(iter);

		cout << ret << '\n';
	}
	return 0;
}

하는 동작은 비슷하지만 STL에서 제공하는 반복자를 통해 인덱스 상태를 관리하고 있습니다. 또한 정답을 출력할 때 printf를 사용하는 것이 속도상 유리하지만(버퍼를 비우지 않으므로), printf가 공식적으로 string 클래스를 지원하지 않기 때문에 c++의 고수준 출력을 사용하되, 적어도 버퍼를 비우지 않도록 endl 대신 '\n'을 사용하였습니다.