코드카타 문제

---

오늘의 코드카타 문제는 다음과 같다.
프로그래머스(쿼드압축 후 자르기) - https://school.programmers.co.kr/learn/courses/30/lessons/68936

간단하게 요약하면, $2^n * 2^n$의 그리드에 0과 1로 값이 채워져있으나, $2^m * 2^m$ 형태로 똑같은 값이 묶여있으면 하나의 값으로 교환한다.

예를 들어서, 다음과 같이 표기가 된다.

이러한 압축 과정으로 0과 1의 개수를 구하는 문제이다.

이 문제의 핵심 아이디어는 다음과 같다.

1. 시작점(0,0)부터 (n-1, n-1)까지 값을 검사한다.
2. 만약 값이 다른 케이스가 나올 경우, 그리드를 균일한 크기로 4등분 한다.
3. 4등분 된 그리드들은 각각 독립적으로 1번의 행동을 반복한다.

그림으로 표현하면 다음과 같이 작성된다.

절반씩 나눠가면서 같은 행동 로직이 반복되므로, 재귀 함수를 사용하여 코드를 작성하였다.

#include <string>
#include <vector>

using namespace std;

// 0과 1의 개수를 반환
vector<int> cnt(2, 0);

void check(const vector<vector<int>>& arr, int row, int col, int length)
{
	// 종료 조건: 크기가 1인 경우
    if (length == 1)
    {
        arr[row][col] == 0 ? cnt[0]++ : cnt[1]++;
        return;
    }
    
    int n = arr[row][col];
    for (int i = 0; i < length; ++i)
    {
        for (int j = 0; j < length; ++j)
        {
        	// 인접한 값과 값이 다르면 재귀 수행
            if (arr[row + i][col + j] != n)
            {
                check(arr, row, col, length / 2);
                check(arr, row, col + length / 2, length / 2);
                check(arr, row + length / 2, col, length / 2);
                check(arr, row + length / 2, col + length / 2, length / 2);
                return;
            }
        }
    }
    
    n == 0 ? cnt[0]++ : cnt[1]++;
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    int length = arr.size();
    
    check(arr, 0, 0, length);
    
    return cnt;
}