[분할정복] 백준 1992번 쿼드트리 (풀이, 해설)

출처 - 백준

 백준 1992번 쿼드트리는 0과 1의 흑백 사진으로 된 파일을 압축하여 표현하는 방법을 활용한 문제입니다.
 문제 난이도는 쉬움이긴 했으나 분할 정복 입문자에게는 다소 어려울 수 있을 듯 합니다.

 제가 푼 풀이 방식은 시작 x좌표, y좌표 그리고 size를 받아서 해당 영역이 모두 같은 값을 가지고 있다면 바로 해당 값을 출력하고 만약에 하나라도 다를 경우 해당 영역을 4등분하여 다시 재귀적으로 검사하도록 하였습니다.

 아래 부터는 제가 작성한 코드입니다.

#include <iostream>

#include <vector>

using namespace std;

void answer(vector< vector<int> >& arr, int y, int x, int size) {

       if (size == 1) {

              cout << arr[y][x];

              return;

       }

       else {

              bool defrent = false;

              int cur = arr[y][x];

              for (int i = y; i < y + size; ++i) {

                     bool brk = false;

                     for (int j = x; j < x + size; ++j) {

                           if (arr[i][j] != cur)

                           {

                                  brk = true;

                                  defrent = true;

                                  break;

                           }

                     }

                     if (brk)

                           break;

              }

              if (defrent) { // 다른것이 있을 경우

                     cout << "(";

                     answer(arr, y, x, size / 2);

                     answer(arr, y, x + size / 2, size / 2);

                     answer(arr, y + size / 2, x, size / 2);

                     answer(arr, y + size / 2, x + size / 2, size / 2);

                     cout << ")";

              }

              else { // 다 동일 할경우

                     cout << arr[y][x];

              }

       }

}

int main() {

       int size;

       cin >> size;

       vector< vector<int> > arr(size, vector<int>(size));

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

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

                     scanf("%1d", &arr[i][j]);

              }

       }

       answer(arr, 0, 0, size);

       return 0;

}

 압축을 해서 출력해주는 위 함수를 사용해서 답을 구했습니다.

 먼저 size가 1인경우에는 해당 수를 출력해주면 되니 출력해주며 종료하게됩니다. 이는 재귀함수에서 기저 사례(탈출조건)으로 작용합니다.

 아닐경우 모두 돌면서 다른 값이 하나라도 있다면, 검사를 중지하고 4개의 영역으로 나누어서(28~31라인) 출력을하게됩니다. 만약에 다 동일한 경우에는 압축하여 출력해주면됩니다.