[프로그래머스] (C++) LV2 쿼드압축 후 개수 세기

흔한 분할정복 문제며, 쿼드트리를 사용하는 문제였다.

자주 보이던 문제 유형이라 어렵진 않았다. 시키는대로 구현하면 된다.

#include <string>
#include <vector>

using namespace std;

vector<int> ans(2, 0);
vector<vector<int>> map;

void QUARD(int start_x, int start_y, int n)
{
    int find_num = map[start_x][start_y];

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if (map[start_x + i][start_y + j] != find_num)
            {
                n /= 2;
                QUARD(start_x, start_y, n);
                QUARD(start_x + n, start_y, n);
                QUARD(start_x, start_y + n, n);
                QUARD(start_x + n, start_y + n, n);
                return;
            }

    ans[find_num]++;
    return;
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    int n = arr.size();
    map = arr;

    QUARD(0, 0, n);

    answer = ans;

    return answer;
}