BOJ - (Algospot) QUADTREE 해결 전략 (C++)

• 문제

  대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다.

  이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다. 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다.
  모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축합니다. 이때 전체 그림의 압축 결과는 x(왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과)(왼쪽 아래 부분의 압축 결과)(오른쪽 아래 부분의 압축 결과)가 됩니다. 예를 들어 그림 (a)의 왼쪽 위 4분면은 xwwwb로 압축됩니다.
 그림 (a)와 그림 (b)는 16×16 크기의 예제 그림을 쿼드 트리가 어떻게 분할해 압축하는지를 보여줍니다. 이때 전체 그림의 압축 결과는 xxwww bxwxw bbbww xxxww bbbww wwbb가 됩니다.

  쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집은 그림 을 쿼드 트리 압축해서 출력하는 프로그램을 작성하세요.

• 입력

  첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 그 후 C줄에 하나씩 쿼드 트리로 압축한 그림이 주어집니다. 모든 문자열의 길이는 1,000 이하이며, 원본 그림의 크기는 220 × 220 을 넘지 않습니다.

• 출력

  각 테스트 케이스당 한 줄에 주어진 그림을 상하로 뒤집은 결과를 쿼드 트리 압축해서 출력합니다.

• 예제 입력
  4
  w
  xbwwb
  xbwxwbbwb
  xxwwwbxwxwbbbwwxxxwwbbbwwwwbb

• 예제 출력
  w
  xwbbw
  xxbwwbbbw
  xxwbxwwxbbwwbwbxwbwwxwwwxbbwb

해결 전략

  본 문제는 '알고리즘 문제 해결 전략 세트' 교재의 Divide & Conquer 파트에 수록된 첫 번째 문제이다. 따라서 본인은 본 문제를 처음 접할 때 당연히 분할정복적 사고를 토대로 접근했는데, 문제의 내용과 보조자료를 읽고 나서 든 생각은, 물론, 재귀적 분할이 필요하긴 하지만, 굳이 이를 Divide & Conquer라고 볼 필요가 있을까 하는 생각이었다.

  주어진 입력을 그대로 실제 '쿼드 트리 자료구조'로 구축하되, '상하 반전되었을 때의 입력 상태'를 고려해 트리를 구축하는 것이다. 그리고 그 트리를 Preorder Traverse하면 됨을 어렵지 않게 확인할 수 있었다. 즉, 이미지로의 변환이나 그런 과정은 (당연히) 필요가 없는 것이다.

  이러한 전략 구축의 근거는, 문제 소개에서 쿼드 트리가 직접적으로 언급되고 있으며, 조건에 의하면 이미지의 크기는 직접 Naive하게 다루기에는 너무나 방대하며, 트리의 구축 과정 자체가 명확히 인지되기 때문이다. 그말은 즉슨, 트리를 구축할 수 있으면, 거기서 간편하게 '무언가 조정'만 하면 해결될 것 같다는 직감이 들었기 때문이다.

  따라서, 본 문제를 해결하는데에 가장 중요한 Skill은 당연 트리를 구축하는 능력이다. 트리는 STL에서 제공하지 않기 때문에 프로그래머의 순수한 자료구조 구축 능력이 필요하다. 다행히도 본인은 자료구조는 작년 꽤나 열심히 공부했기에 현재의 PS 수준에 비해서는 그래도 준수한 구축 능력을 갖추고 있었다.

  아래는 코드이다. 보다 더 자세한 설명은 주석을 통해 대체한다.

#include <iostream>
#include <string>
// Algospot - QUADTREE
using namespace std;

// x (xwwwb)(xw(xwbbb)ww)(x(x(xwwbb)bww)wwb)b
// xxwwwbxwxwbbbwwxxxwwbbbwwwwbb

string image;
int index;

typedef struct _node{	// 쿼드 트리를 구축하기 위한 기본 구조체
	char data;
	struct _node *upleft;	// NODE라는 명칭은 link 설정 시점 이후에 정의되기에
	struct _node *upright;	// struct _node로 변수를 정의해야함에 주의!
	struct _node *downleft;
	struct _node *downright;
}NODE;

NODE* makeTree(void) {				// 쿼드트리를 구축하는 함수
	NODE *newNode = new NODE;		// 호출 시마다 NODE 할당

	if (index >= image.size())		// index 변수는 image라는 스트링을 매 호출마다
		return NULL;				// 조회하는 변수로, 호출시마다 1씩 increment된다.
	// 따라서 index가 image 스트링의 마지막 인덱스보다 큰 경우엔 함수는 널을 반환한다.
	newNode->data = image[index];
	index++;

	if (newNode->data == 'x') {		// 문제 상황에 따라 x인 경우엔 아래와 같이 재귀적
		newNode->downleft = makeTree();		// 으로 4개의 자식노드를 연결한다.
		newNode->downright = makeTree();	// 인덱스 변수의 도입은 바로 이 부분에서
		newNode->upleft = makeTree();		// 스트링의 각 요소를 이 흐름에 맞게 접근
		newNode->upright = makeTree();		// 하기 위함이다.
		// 이때, 상하를 뒤집기 위해 down링크부터 연결하고 있음을 주목
	}
	else {	// x가 아닌 경우엔 말단노드이므로
		newNode->upleft = newNode->upright
			= newNode->downleft = newNode->downright = NULL;
	}

	return newNode;
}

void readTree(NODE *node) {	// 문제 상황과 쿼드 트리의 구조 고려 시 전위순회가 올바름.
	if (node != NULL) {
		cout << node->data;
		readTree(node->upleft);
		readTree(node->upright);
		readTree(node->downleft);
		readTree(node->downright);
	}
}

int main(void) {
	int C;

	cin >> C;
	while (C--) {
		cin >> image;

		index = 0;
		NODE* root = makeTree();
		readTree(root);
		cout << endl;
		
		image.clear();	// 각 테스트 케이스마다 초기화해주는 것 중요
	}

	return 0;
}