C++:: 프로그래머스 < 쿼드압축 후 개수 세기 >

쿼드 트리와 같은 형태로 주어진 arr을 재귀를 통해 쪼갤수 없을때 까지 쪼개주면서 더 이상 쪼갤 수 없을 때의 데이터의 개수를 늘려 answer를 리턴하면 되는 문제이다. 전형적인 재귀문제의 느낌으로 크게 어렵지 않다.

#include <string>
#include <vector>

using namespace std;
vector<int> answer(2,0);

void recur(int sRow, int eRow, int sCol, int eCol, vector<vector<int>> *arr) {
    int data = (*arr)[sRow][sCol];// 현재 구간의 대표 데이터
    bool dividable = false;
    for (int i=sRow; i<eRow && !dividable; i++) {
        for (int j=sCol; j<eCol && !dividable; j++) {
            if ((*arr)[i][j] != data) dividable = true;// 대표 데이터와 다르다면 
        }
    }
    if (!dividable) {// 더이상 쪼갤 수 없다면
        answer[data]++;
    } else {// 쪼갤 수 있다면 4개의 사분면으로 쪼개준다.
        recur(sRow, (sRow+eRow)/2, sCol, (sCol+eCol)/2, arr);// 1사분면
        recur(sRow, (sRow+eRow)/2, (sCol+eCol)/2, eCol, arr);// 2사분면
        recur((sRow+eRow)/2, eRow, sCol, (sCol+eCol)/2, arr);// 3사분면
        recur((sRow+eRow)/2, eRow, (sCol+eCol)/2, eCol, arr);// 4사분면
    }
}

vector<int> solution(vector<vector<int>> arr) {
    int size = arr.size();
    recur(0, size, 0, size, &arr);
    return answer;
}