[ 프로그래머스 ] 쿼드압축 후 개수 세기

문제

---

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

풀이

---

주어진 2차원 정수 배열을 쿼드 트리와 같은 방식으로 압축하는 문제로, 주어진 배열을 균일하게 압축하기 위해, 같은 숫자로 이루어져 있지 않은 2차원 정수 배열의 행과 열을 2로 나눠 4개의 2차원 정수 배열을 만든다. 그리고 이 배열들이 같은 숫자로 이루어지거나, 더 이상 나눌 수 없을 때까지 나누는 것을 반복하여 여러 개의 같은 숫자로 이루어진 배열의 개수를 return한다.

#include <string>
#include <vector>

using namespace std;

vector<int> answer;
vector<vector<int>> nodes;

void QuadTree(int node_distance, int y, int x)
{
    if (node_distance == 1)
    {
        if (nodes[y][x] == 0)
        {
            answer[0]++;
        }

        else
        {
            answer[1]++;
        }

        return;
    }

    bool isOne = true;
    bool isZero = true;

    for (int i = y; i < y + node_distance; i++)
    {
        for (int j = x; j < x + node_distance; j++)
        {
            if (nodes[i][j] == 1)
            {
                isOne = false;
            }

            else
            {
                isZero = false;
            }

            if (isOne == false && isZero == false)
            {
                break;
            }
        }

        if (isOne == false && isZero == false)
        {
            break;
        }
    }

    if (isZero)
    {
        answer[1]++;
    }

    else if (isOne)
    {
        answer[0]++;
    }

    else
    {
        QuadTree(node_distance / 2, y, x);
        QuadTree(node_distance / 2, y, x + node_distance / 2);
        QuadTree(node_distance / 2, y + node_distance / 2, x);
        QuadTree(node_distance / 2, y + node_distance / 2, x + node_distance / 2);
    }

    return;
}


vector<int> solution(vector<vector<int>> arr) 
{

    nodes = arr;
    answer.push_back(0);
    answer.push_back(0);

    QuadTree(arr[0].size(), 0, 0);


    return answer;
}