[Algorithm] Programmers :: 쿼드압축 후 개수 세기

https://school.programmers.co.kr/learn/courses/30/lessons/68936

프로그래머스

struct Node
{
    int y;
    int x;
 
    Node& operator+=(const Node& a)
    {
        this->y += a.y;
        this->x += a.x;
 
        return *this;
    }
};
 
Node divide(Node leftTop, int n, vector<vector<int>>& arr)
{
    if (n == 1)
    {
        if (arr[leftTop.y][leftTop.x] == 0) return { 1,0 };
        else return { 0,1 };
    }
 
    int standard = arr[leftTop.y][leftTop.x];
    bool isBreak = false;
 
    for (int i = leftTop.y; i < leftTop.y + n; ++i)
    {
        for (int j = leftTop.x; j < leftTop.x + n; ++j)
        {
            if (arr[i][j] != standard)
            {
                isBreak = true;
                break;
            }
        }
 
        if (isBreak) break;
    }
 
    if (!isBreak)
    {
        if (standard == 0) return { 1,0 };
        else return { 0,1 };
    }
 
    Node result = { 0,0 };
 
    result += divide(leftTop, n / 2, arr); // 좌측 상단
    result += divide({ leftTop.y ,leftTop.x + n / 2 }, n / 2, arr); // 우측 상단
    result += divide({ leftTop.y + n / 2, leftTop.x }, n / 2, arr); // 좌측 하단
    result += divide({ leftTop.y + n / 2, leftTop.x + n / 2 }, n / 2, arr); // 우측 하단
 
    return result;
}
 
 
vector<int> solution(vector<vector<int>> arr)
{
    vector<int> answer;
 
    Node temp = divide({ 0,0 }, arr.size(), arr);
 
    return answer = { temp.y, temp.x };
}

재귀를 통해 각 사분면을 계속 파고들어 개수를 구하면 되는 문제이다.

0의 개수랑 1의 개수를 같이 리턴해야해서 연산자오버로딩해서 좀 더 깔끔하게 해봤다.