[종만북 문제] 쿼드 트리 뒤집기 (문제 ID : QUADTREE, 난이도 : 하)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 단순하게 생각해라

---

[종만북 문제] 쿼드 트리 뒤집기 (문제 ID : QUADTREE, 난이도 : 하)

음.. 쿼드 트리는 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 하나이다. 쿼드 트리는 주어진 공간을 항상 4개로 분할하여 재귀적으로 저장하는데, 이번에는 검은색/흰색밖에 없는 그림을 압축한 예제를 풀어 볼 것이다. 😎

 

일단 단순히 재귀적으로만 풀면, 아래와 같이 풀어볼 수도 있다(책에 나온 버전은 그 다음에 소개할 것임).

#include <iostream>
#include "stdlib.h"
#include <vector>

using namespace std;

#define MINVAL(x, y) (((x) > (y)) ? y : x)
#define MAXVAL(x, y) (((x) > (y)) ? x : y)

/****************************************************************************************************/
/****************************************************************************************************/
/****************************************************************************************************/

struct node
{
	char c;
	vector<node*> children;

	node() = default;
	node(node* newNode)
	{
		c = newNode->c;
		for (int i = 0; i < newNode->children.size(); ++i)
		{
			children.push_back(new node(newNode->children[i]));
		}
	}
};

string ans;
vector<char> inputs;
node* head;

node* makeTree(node* parent, int& idx)
{
	if (inputs.size() <= idx)
		return parent;

	if (parent->c == 'x')
	{
		for (int i = 0; i < 4; ++i)
		{
			node* child = new node;
			child->c = inputs[++idx];

			parent->children.push_back(makeTree(child, idx));
		}
	}

	return parent;
}


void reverseTree(node* cur)
{
	if (nullptr == cur)
		return;

	if (cur->c == 'x')
	{
		for (int i = 0; i < 4; ++i)
			reverseTree(cur->children[i]);
		
		node* temp1 = cur->children[0];
		node* temp2 = cur->children[1];
		cur->children[0] = cur->children[2];
		cur->children[1] = cur->children[3];
		cur->children[2] = temp1;
		cur->children[3] = temp2;
	}
}

void printTree(node* cur)
{
	if (nullptr == cur)
		return;

	cout << cur->c;

	for (int i = 0; i < cur->children.size(); ++i)
		printTree(cur->children[i]);
}

void sol()
{
	head = new node;
	head->c = inputs[0];

	int idx = 0;
	makeTree(head, idx);

	reverseTree(head);

	printTree(head);

	cout << endl;
}

void outputHandler()
{
	sol();
}

void inputHandler()
{
	inputs.clear();

	string input;
	cin >> input;
	for (char c : input)
		inputs.push_back(c);
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		inputHandler();

		outputHandler();
	}

	return 0;
}

그냥 makeTree 로 트리 구조를 만들고, reverseTree 로 재귀적으로 child 노드들을 뒤집으면 해결이 된다.

 

그런데, 그랜드 소드 마스터 구종만 선생님은 이 문제를 어떻게 푸셨을까? 일단, 다음과 같이 crude 한 압축 해제 구현을 만들어 볼 수 있다. 아래 코드는 문자열을 나눠가면서 압축 해제한다.

constexpr int MAX_SIZE = 1000;
char decompressed[MAX_SIZE][MAX_SIZE];

void decompress(string::iterator& it, int y, int x, int size)
{
	// 한 글자를 검사할 때마다 반복자를 한 칸 앞으로 옮긴다.
	char head = *(it++);
	
	// 기저 사례 : 첫 글자가 b 또는 w 인 경우
	if (head == 'b' || head == 'w')
	{
		for (int dy = 0; dy < size; ++dy)
			for (int dx = 0; dx < size; ++dx)
				decompressed[y+dy][x+dx] = head;
	}
	else
	{
		// 네 부분을 각각 순서대로 압축 해제한다.
		int half = size / 2;
		decompress(it, y, x, half);
		decompress(it, y, x + half, half);
		decompress(it, y + half, x, half);
		decompress(it, y + half, x + half, half);
	}
}

 

그런데 사실, 결과를 굳이 저장하지 않고 reverse 라는 함수 하나로도 풀 수 있다.

#include <iostream>
#include "stdlib.h"
#include <vector>

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;
}

void sol()
{
	string input;
	cin >> input;
	auto itr = input.begin();
	cout << reverse(itr) << endl;
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		sol();
	}

	return 0;
}

아, 이거 ㄹㅇ 실화냐? 구종만 선생님은 전설이다. 진짜 세계관최강자의 코드다...