분할 정복 (프로그래머스: 쿼드압축 후 개수 세기)

📍 분할 정복

---

✔ 접근 방법

• 2차원 배열 arr의 (row, col)위치부터 행 row ~ row + size, 열 col ~ col + size 만큼 모두 같은 숫자인지 검사

// val: arr[row][col] 값
static boolean isOk(int[][] arr, int size, int row, int col, int val) {
        for (int r = row; r < row + size; r++)
            for (int c = col; c < col + size; c++)
                if (arr[r][c] != val)
                    return false;
        return true;
    }

• 압축할 수 없다면, size의 크기 반으로 줄여야 함 (size / 2)
  • 분할해서 size/2의 사이즈 2차원 배열 처음 검사 위치
    ➡ (x, y), (x, y + size/2), (x + size/2, y), (x + size/2, y + size/2)

static void quad(int[][] arr, int size, int r, int c) {
    int val = arr[r][c];

    // 압축 가능한지 체크
    if (isOk(arr, size, r, c, val)) {
        // 0인지 1인지 판단
        check(val);
        return; // 재귀
    }

    // 압축 불가능한 경우 size 감소
    size = size / 2;

    quad(arr, size, r, c);
    quad(arr, size, r, c + size);
    quad(arr, size, r + size, c);
    quad(arr, size, r + size, c + size);

 }

✔ 전체 코드

class Solution {

    static int one, zero;

    public int[] solution(int[][] arr) {
        one = 0;
        zero = 0;

        quad(arr, arr.length, 0, 0);

        return new int[] { zero, one };
    }

    static void quad(int[][] arr, int size, int r, int c) {
        int val = arr[r][c];

        // 압축 가능한지 체크
        if (isOk(arr, size, r, c, val)) {
            // 0인지 1인지 판단
            check(val);
            return; // 재귀
        }

        // 압축 불가능한 경우 size 감소
        size = size / 2;

        quad(arr, size, r, c);
        quad(arr, size, r, c + size);
        quad(arr, size, r + size, c);
        quad(arr, size, r + size, c + size);

    }

    static boolean isOk(int[][] arr, int size, int row, int col, int val) {
        for (int r = row; r < row + size; r++)
            for (int c = col; c < col + size; c++)
                if (arr[r][c] != val)
                    return false;
        return true;
    }

    static void check(int val) {
        if (val == 1)
            one++;
        else
            zero++;
    }
}