쿼드압축 후 개수 세기 / 재귀

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

2차원 배열 arr가 주어지고, 이걸 쿼드 트리 방식으로 압축했을 때 최종적으로 남는 0의 개수와 1의 개수를 세는 문제이다.
재귀호출을 하며 현재 사각형 배열의 값이 모두 같다면 더 이상 쪼갤 필요 없이 바로 압축이 가능하고, 그렇지 않으면 다시 4등분해서 각각에 대해 다시 압축을 시도해야했고, 이 과정을 재귀호출로 계속 반복했다.

 

✅ 재귀호출로 문제 해결 코드

#include <string>
#include <vector>

using namespace std;

pair<int, int> compress(const vector<vector<int>>& arr, int y, int x, int size)
{
    int base = arr[y][x];
    bool allsame = true;

    for (int i = y; i < y + size; ++i)
    {
        for (int j = x; j < x + size; ++j)
        {
            if (arr[i][j] != base)
            {
                allsame = false;
                break;
            }
        }
        if (!allsame) break;
    }

    // 현재 사각형에 모든 값이 같을 경우
    if (allsame)
    {
        return (base == 0) ? make_pair(1, 0) : make_pair(0, 1);
    }

    // 현재 사각형에 모든 값이 같지 않을 경우
    int half = size / 2;
    pair<int, int> result1 = compress(arr, y, x, half);
    pair<int, int> result2 = compress(arr, y, x + half, half);
    pair<int, int> result3 = compress(arr, y + half, x, half);
    pair<int, int> result4 = compress(arr, y + half, x + half, half);

    return {
        result1.first + result2.first + result3.first + result4.first,
        result1.second + result2.second + result3.second + result4.second
    };
}

vector<int> solution(vector<vector<int>> arr) 
{
    int size = arr.size();
    pair<int, int> result = compress(arr, 0, 0, size);

    vector<int> answer = { result.first, result.second };
    return answer;
}

 

✅ 입출력 예제 1번 케이스

int main()
{
    vector<vector<int>> test = 
    {
        {1,1,0,0},
        {1,0,0,0},
        {1,0,0,1},
        {1,1,1,1}
    };

    vector<int> answer = solution(test);

    return 0;
}

첫 번째로 compress 함수 호출로 들어갔을 때, 배열 내의 모든 숫자가 일치하지 않기 때문에, 4등분으로 재귀호출을 시작한다.
result1은 0이 1개, 1이 3개 값을 도출하였고, 우측 result2는 모든 값이 0이므로 {1, 0}의 값을 도출하였다.
같은 방식으로 result3과 result4를 계산하고, 계산된 모든 값을 더해 최종 {4, 9}의 값을 도출할 수 있게 되었다.

처음엔 문제해결을 어떻게 접근해야될지 감이 도무지 잡히지 않았는데, 결론적으로 현재 주어진 배열의 값이 모두 같지 않으면 계속 4등분을 하여 깊게 들어간다고 생각해보니, 재귀호출을 사용해야된다고 판단이 되었다.