[QUADTREE] 쿼드 트리 뒤집기

문제

대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(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

---

문제 풀이

쿼드 트리는 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하는 기법이다. 이의 유명한 사용처는 하나는 흰 색과 검은 색밖에 없는 흑백 그림을 압축해 표현하는 것.

• 그 부분의 모든 픽셀이 검은 색이면 쿼드 트리 압축 결과는 b이다.
• 그 부분의 모든 픽셀이 흰 색일 경우 쿼드 트리 압축 결과는 w이다.
• 모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축 합니다. 이때 전체 그림의 압축 결과는 x(왼쪽 위)(오른쪽 위)(왼쪽 아래)(오른쪽 아래)가 된다.

분할 정복이 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제들로 나누는 것이다.

가장 간단한 방법은 입력 받은 쿼드 트리 압축을 풀어 이미지로 변환하고 그 이미지를 상하 반전 한 후 다시 압축 하는 방법이다. 하지만 입력크기가 매우 크게 들어올 수도 있기 때문에 이 방식은 시간 초과나 메모리 초과가 날 확률이 높다.

1. 쿼드 트리 압축 풀기

문자열 s이 압축을 해제해서 nxn 크기의 배열에 저장하는 함수 decompress를 구현해보자.

p.193

2. 압축을 다 풀지 않고 뒤집기

1번 방법은 압축을 해제한 결과를 메모리에 다 저장한다는 점에서 그림의 크기가 커진다면 엄청난 메모리를 사용할 것이다. 그렇기 때문에 결과 이미지를 뒤집은 결과를 바로 생성하는 코드를 짜는 것이 좋겠다.

전체가 한 가지 색이 아니라면 재귀 호출을 이용해 네 부분을 각각 상하로 뒤집은 결과를 얻은 뒤, 이를 병합해 답을 얻으면 된다.

이때 병합할때 4가지 부분을 모두 뒤집은 후 위 두 조각과 아래 두 조각을 각각 바꾸면 전체를 한번에 상하로 뒤집은 것과 같은 결과를 낼 수 있다.

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

string reverse(string::iterator &it) {
	char head = *(it++); // iter의 첫번째 글자 판단
	if (head == 'b' || head == 'w') { // 뒤집어도 동일
		return string(1,head);
	}
	// 다시 4등분해서 표현
		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() {
	int case_test;
	cin >> case_test;
	while (case_test!=0) {
		string str;
		cin >> str;
		string::iterator it = str.begin();
		cout << reverse(it) << endl;
		case_test--;
	}
}

iterator를 이용해서 입력 받은 string을 하나씩 순회하며 뒤집는다.

문자열이 x라면 자식이 4개인 tree를 만든다고 생각하면 된다. x가 아니라면 b, w는 상하 반전해도 동일함으로 그냥 입력한다.

x라면 2등분해 왼쪽 위, 왼쪽 아래, 오른쪽 위, 오른쪽 아래로 나눈 후 x가 안 나올때까지 그 과정을 반복한다.  그 후 그 string을 다시 반전하여 합쳐주면 된다.

---

코드가 매우 직관적이고 간단한 코드다. 하지만 내 머리로는 혼자 못 만들었을 것 같다,, 힘드렁