[알고리즘 문제해결 전략] 쿼드 트리 뒤집기

문제출처

• [알고리즘 문제해결 전략1] - 7장 분할정복 예제
• 소스코드는 구현한 함수의 동작 여부를 관찰하기 위해 본인의 테스트 코드를 추가하여 작성한 결과이다.

문제 설명

• 2^N X 2^N 크기의 흑백 그림이 주어질 때, 이 그림을 상하로 뒤집은 그림의 쿼드 트리 압축 결과를 출력하라.
• 그림의 모든 픽셀이 검은 색일 경우 압축결과는 크기 상관없이 b가 된다.
• 그림의 모든 픽셀이 흰 색일 경우 압축결과는 크기 상관없이 w가 된다.
• 그림 안에 모든 픽셀이 같은 색이 아닌 경우 그 그림을 1/4로 자른다.
• 위 과정을 반복한다.

문제 접근 방향 (bokyoung)

• 압축을 어떻게 풀어야 할지부터 막혔다..
• x를 만나면 무조건 분할되는 형태…
• 압축을 해제하고 이미지를 만든 다음 상하로 뒤집어서 다시 압축을 하는 것은… 메모리 초과가 남

문제 접근 방향 (Solution)

• 쿼드 트리가 재귀적으로 정의되어 있기 때문에 쿼드 트리를 압축하거나 해제하는 과정은 재귀 호출로 구현하는 것이 가장 자연스럽다.
• 문자열 s의 압축을 해제해서 이미지를 만드는 함수 decompress()를 구현해본다.
  • s의 첫글자가 w나 b인 경우 그 영역 전체에 해당 색을 칠한다.
  • s의 첫글자가 x라면 decompress()는 나머지 영역을 4개로 쪼개 재귀호출 한다.
  • 각 영역이 배열의 어느 부분을 나타내는지 알려주기 위해 위치 오프셋도 함께 전달한다.
• 압축을 다 풀지 않고 뒤집는 방법으로 결과를 곧장 생성하도록 한다.
  • 전체가 검은색이거나 흰색인 경우 뒤집어도 똑같다.
  • 전체가 한 가지 색이 아닌 경우 재귀 호출을 이용해 네 부분을 각각 상하로 뒤집은 결과를 얻은 뒤, 이를 병합해 답을 얻는다.

구현결과

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

#define MAX_SIZE 10000

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

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 print_map(int n) {
	for (int r = 0; r < n; r++) {
		for (int c = 0; c < n; c++)
			cout << decompressed[r][c] << " ";
		cout << endl;
	}
}

int main()
{
	string str;
	cin >> str;
	string::iterator iter = str.begin();

	decompress(iter, 0, 0, 16);
	print_map(16);
	cout << endl;
	cout << "-----------After reversing---------------" << endl;

	iter = str.begin();
	string rstr = reverse(iter);
	iter = rstr.begin();
	decompress(iter, 0, 0, 16);
	print_map(16);
	cout << endl;
	cout << "reverse image: " << rstr << endl;
}

Test Case

입력
xxwwwbxwxwbbbwwxxxwwbbbwwwwbb

출력
w w w w w w w w w w w w w w b b
w w w w w w w w w w w w w w b b
w w w w w w w w w w w w b b b b
w w w w w w w w w w w w b b b b
w w w w b b b b w w w w w w w w
w w w w b b b b w w w w w w w w
w w w w b b b b w w w w w w w w
w w w w b b b b w w w w w w w w
w w b b w w w w b b b b b b b b
b b b b w w w w b b b b b b b b
w w w w w w w w b b b b b b b b
w w w w w w w w b b b b b b b b
w w w w b b b b b b b b b b b b
w w w w b b b b b b b b b b b b
w w w w b b b b b b b b b b b b
w w w w b b b b b b b b b b b b

-----------After reversing---------------
w w w w b b b b b b b b b b b b
w w w w b b b b b b b b b b b b
w w w w b b b b b b b b b b b b
w w w w b b b b b b b b b b b b
w w w w w w w w b b b b b b b b
w w w w w w w w b b b b b b b b
b b b b w w w w b b b b b b b b
w w b b w w w w b b b b b b b b
w w w w b b b b w w w w w w w w
w w w w b b b b w w w w w w w w
w w w w b b b b w w w w w w w w
w w w w b b b b w w w w w w w w
w w w w w w w w w w w w b b b b
w w w w w w w w w w w w b b b b
w w w w w w w w w w w w w w b b
w w w w w w w w w w w w w w b b

reverse image: xxwbxwwxbbwwbwbxwbwwxwwwxbbwb

쿼드 트리(quad tree)

• 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 기법 중 하나
• 주어진 공간을 항상 4개로 분할해 재귀적으로 표현한다.
• 유명한 사용처 중 하나는 흑백 그림을 압축해 표현하는 것