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

class Solution {
    int[] answer = new int[2];
    public int[] solution(int[][] arr) {
        zip(arr, 0, 0, arr.length);

        return answer;
    }
    
     private  void zip(int[][] arr, int sx, int sy, int size) {

        if (check(arr, sx, sy, size)) {
            answer[arr[sy][sx]]++;
            return;
        }

        int middle = size / 2;

        zip(arr, sx, sy, middle);
        zip(arr, sx, sy + middle, middle);
        zip(arr, sx + middle, sy, middle);
        zip(arr, sx + middle, sy + middle, middle);
    }

    private  boolean check(int[][] arr, int sx, int sy, int size) {

        int num = arr[sy][sx];

        for (int y = sy; y < sy + size; y++) {
            for (int x = sx; x < sx + size; x++) {
                if (num != arr[y][x])
                    return false;
            }
        }

        return true;
    }
}

🤔분할 정복 방식으로 푸는 문제입니다.
2차원 배열을 4분의 1씩 쪼개면서 해당 구간이 전부 같은 숫자인지 체크를 해주면 되는 문제입니다.
😑2차원 배열을 4분의 1씩 쪼개는 방법은 다음과 같이 할 수 있습니다:

1. 먼저 해당 배열이 모두 같은 숫자로 이루어져 있는지 체크합니다. 만약 같다면 정답값에 더해주고 아니라면 다음 단계를 진행합니다.
2. 배열의 사이즈의 반을 기준으로 (왜냐하면 2n*2n크기의 배열이기 때문에 반반으로 나눈다고 생각하시면 됩니다.)배열의 행과 열을 반으로 나눕니다.
3. 각 사분면을 다시 재귀형태로 함수에 넣어줍니다. 다시 1~2과정을 거칩니다.

출처: 프로그래머스 - 쿼드압축 후 개수 세기