7.2_쿼드 트리 뒤집기_QUADTREE

문제 설명

 

algospot.com :: QUADTREE

• 쿼드 트리 = 주어진 공간을 4분할해 재귀적으로 표현한 것
• 해당 영역의 모든 픽셀이 검정이면 b
• 해당 영역의 모든 픽셀이 흰색이면 w
• 둘 다 아니면 쪼개져 들어간 후 압축하여 x(왼쪽 위)(오른쪽 위)(왼쪽 아래)(오른쪽 아래)

=> 쿼드 트리로 압축된 그림이 주어졌을 때, 상하로 뒤집은 그림을 쿼드 트리로 압축하여 출력하기

 

 

문제 풀이

우선 이 문제에서 주어지는 그림의 크기는 최대  2^20 × 2^20 이므로

쿼드 트리를 직접 그린 후 다시 압축하는 방법은 적합하지 않다.

 

그렇다면 주어진 쿼드 트리 그대로 상하반전된 쿼드 트리를 도출해내야 하는데,

문제에서 주어지는 쿼드 트리는 x(좌상)(우상)(좌하)(우하) 이고

상하로 그림을 뒤집는다 하면, 위(상)에 있는 픽셀은 아래로, 아래(하)에 있는 픽셀은 위로 올라갈 것이므로

x(좌하)(우하)(좌상)(우상)으로 표현될 것이다.

 

쿼드 트리에서 x라는 것은 해당 영역을 4분할 하는 것을 의미한다.

나는 이 점에서 힌트를 가져왔다.

 

1.

4분할 => 알파벳 개수가 4개 추가됨

을 의미하므로

    b, w : 그 자체로 한 영역

    x : x + 4묶음(알파벳 하나일 수도 있고 여러개일 수도 있음)

을 이용해 한 영역당 있어야 할 알파벳의 개수를 세었다.

 

2.

그리고 각 영역을 나타내는 시작 인덱스를 배열에 저장한 후

좌하(2) -> 우하(3) -> 좌상(0) -> 우상(1) 순으로

재귀를 타고 내려가도록 구현했다.

 

3. 재귀를 타고 내려가 flipedQuadtree(뒤집힌 쿼드 트리, 정답 배열)에 해당 순서대로 영역 값을 입력하도록 했다.

 

4. 입력된 알파벳의 개수(writeIndex)를 반환하고, 다음 영역 탐색 시 그 다음 위치부터 입력하도록 했다.

 

문제 풀이 코드

// 기존 : 좌상-우상-좌하-우하
// 상하반전 : 좌하-우하-좌상-우상

// 2^20 x 2^20 이면 직접 그리는 문제는 아니겠지

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

#define MAXSIZE 1000

using namespace std;

char originalQuadtree[MAXSIZE];
char flipedQuadtree[MAXSIZE];

void MakeQuadTree(int startIndex, int endIndex, int writeIndex) {
	if (endIndex - startIndex == 1) {	// 알파벳 1개
		flipedQuadtree[writeIndex] = originalQuadtree[startIndex];
		return;
	}
	else if (endIndex - startIndex == 5) {	// x + 알파벳 4개
		flipedQuadtree[writeIndex++] = originalQuadtree[startIndex];
		flipedQuadtree[writeIndex++] = originalQuadtree[startIndex + 3];
		flipedQuadtree[writeIndex++] = originalQuadtree[startIndex + 4];
		flipedQuadtree[writeIndex++] = originalQuadtree[startIndex + 1];
		flipedQuadtree[writeIndex++] = originalQuadtree[startIndex + 2];
		return;
	}

	flipedQuadtree[writeIndex++] = originalQuadtree[startIndex++];	// x

	int quadIndexArr[4];				// 4분할의 시작index 저장 배열
	int quadIndexStart = startIndex;	// for문을 도는 동안의 4분할 시작 index
	int quadCount = 0;					// 지금까지 센 4분할 칸 개수
	int goalCount = 1;					// 4분할의 한 칸을 차지할 알파벳 총 개수
	int count = 0;						// 알파벳 개수
	for (int i = startIndex; i < endIndex; ++i) {
		if (originalQuadtree[i] == 'x') {	// x가 있다면 알파벳 4개 더 있어야 함
			goalCount += 4;
		}
		++count;

		if (count == goalCount) {
			quadIndexArr[quadCount++] = quadIndexStart;
			quadIndexStart = i + 1;
			goalCount = 1;
			count = 0;
		}
	}

	MakeQuadTree(quadIndexArr[2], quadIndexArr[3], writeIndex);	//좌하
	writeIndex += quadIndexArr[3] - quadIndexArr[2];

	MakeQuadTree(quadIndexArr[3], endIndex, writeIndex);		//우하
	writeIndex += endIndex - quadIndexArr[3];

	MakeQuadTree(quadIndexArr[0], quadIndexArr[1], writeIndex);	//좌상
	writeIndex += quadIndexArr[1] - quadIndexArr[0];

	MakeQuadTree(quadIndexArr[1], quadIndexArr[2], writeIndex);	//우상
}

int main(void) {
	int C;
	cin >> C;

	for (int tc = 1; tc <= C; ++tc) {
		memset(originalQuadtree, 0, sizeof(char) * MAXSIZE);
		memset(flipedQuadtree, 0, sizeof(char) * MAXSIZE);
		cin >> originalQuadtree;
		
		// 총 길이 재기
		int cnt = 0;
		while (originalQuadtree[cnt] != 0) {
			cnt++;
		}

		MakeQuadTree(0, cnt, 0);

		cout << flipedQuadtree << endl;
	}

	return 0;
}