2. Divide & Conquer - 쿼드트리(quadtree) 문제 (1992)

주어진 영상을 4등분하여 각각의 영역에 대해 압축을 한다.

이 때 해당 영역이 모두 같은 숫자면 바로 압축하고, 영역의 숫자들이 다르면 또 다시 4등분하여 과정을 반복한다.

크기가 1이 되면 무조건 해당 원소를 리턴한다.

문제 풀이

#include <iostream>

#include <vector>

using namespace std;

vector<char> result;

void compress(int n, vector< vector<int> >& video) {

//base case : 사이즈가 1이면 해당값 바로 리턴

if (n == 1) {

result.push_back(video[0][0]+'0');

return;

}

// base case : 해당 파트의 모든 원소가 같으면 해당값 리턴

int check = video[0][0];  // 영상의 첫번째 원소와 다른 원소들을 비교

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

if (video[i][j] != check) {  // 첫번째 원소와 값이 다르면 check값 변경시킴

check++;

break;

}

}

if (check != video[0][0]) break;

}

if (check == video[0][0]) {  // check값이 변화가 없이 첫번째 원소값을 저장하고 있으면 모든 원소가 같은값임

result.push_back(check+'0');

return;

}

int half = n / 2;

vector< vector<int> > halfVd; // 4등분한 영상

for (int i = 0; i < half; i++) {

vector<int> element(half);

halfVd.push_back(element);

}

// 입력받은 영상을 4등분해서 각 영역에 대해 압축을 실행한다.

result.push_back('(');

for (int domain = 0; domain < 4; domain++) {

// halfVd에 4등분한 해당 영역을 복사한다.

for (int i = 0; i < half; i++) {

for (int j = 0; j < half; j++) {

if (domain == 0) halfVd[i][j] = video[i][j];

else if (domain == 1) halfVd[i][j] = video[i][j + half];

else if (domain == 2) halfVd[i][j] = video[i + half][j];

else halfVd[i][j] = video[i + half][j + half];

}

}

compress(half, halfVd);

}

result.push_back(')');

}

int main() {

int n;

vector< vector<int> > input;

cin >> n;

// 이중 벡터 동적 할당

for (int i = 0; i < n; i++) {

vector<int> element(n);

input.push_back(element);

}

// 영상 입력받음

for (int i = 0; i < n; i++) {

char line[64];

cin >> line;

for (int j = 0; j < n; j++) {

input[i][j] = line[j] - '0';

}

}

compress(n, input);

for (int i = 0; i < result.size(); i++) {

cout << result[i];

}

cout << endl;

return 0;

}

쿼드 트리 뒤집기 문제

이 문제의 경우 압축되어 있는 문자열을 압축을 풀어 그림을 다시 만든 후, 상하로 뒤집은 그림을 다시 압축해야한다.

그런데 그림의 사이즈가 최대 2^20 * 2^20 까지 될 수 있으므로, 그림의 크기가 커질 경우에는 압축을 다 푸는 것이 불가능하다.

따라서 압축을 풀지않고 문제를 해결하도록 한다.

// 쿼드 트리 뒤집기 문제를 해결하는 분할 정복 알고리즘

string reverse(string::iterator& it){

char head = *it;

it++;  // 다음 위치를 가리키게 한다.

// base case : 현재 가리키고 있는 원소가 b 또는 w 이면 그 원소를 리턴한다.

if(head == 'b' || head == 'w') return string(1, head);

// 현재 가리키고 있는 원소가 x 이면 뒤의 문자열들을 네 부분으로 나눈다.

string upperLeft = reverse(it);

string upperRight = reverse(it);

string lowerLeft = reverse(it);

string lowerRight = reverse(it);

// 각각 상하를 반전시킨다.

return string("x") + lowerLeft + lowerRight + upperLeft + upperRight;

}