---

사용한 알고리즘 : 분할정복

• 주어진 문제를 더 작은 하위 문제로 분할하여 각각 해결한 후, 결과를 합쳐 전체 문제를 해결.
  해당 문제는 배열을 4등분하여 각 부분 영역을 처리

---

📌flag 함수

해당 함수의 목적

• 주어진 arr 배열의 (x, y)에서 시작하는 size x size 크기의 영역이 모두 동일한 값을 가지는지 확인
• arr : 원본 배열
• x : 시작 행 인덱스
• y : 시작 열 인덱스
• size : 검사할 영역의 크기

해당 영역을 순회하며, 모든 값이 val 과 동일한지 확인
만약 하나라도 다르면 false 를 반환하고 모두 같다면 true를 반환

public boolean flag(int[][] arr, int x, int y, int size) {
    int val = arr[x][y];
    for (int i = x; i < x + size; i++) {
        for (int j = y; j < y + size; j++) {
            if (arr[i][j] != val) {
                return false;
            }
        }
    }
    return true;
}

---

📌zip 함수

해당 함수의 목적

• 주어진 영역이 동일한 값으로 압축 가능한지 확인하고, 가능하면 해당 값을 answer에 기록, 그렇지 않으면 영역을 4등분 하여 재귀적으로 처리
• arr : 원본 배열
• x : 시작 행 인덱스
• y : 시작 열 인덱스
• size : 검사할 영역의 크기
• answer : 0과 1의 개수를 기록하는 배열

flag 함수를 사용해 주어진 영역이 동일한 값으로 구성되어 있는지 확인. 만약 동일하다면 해당 값을 answer 배열에 기록하고, 그렇지 않다면 영역을 4등분하여 각각에 대해 zip 함수를 재귀적으로 호출

public void zip(int[][] arr, int x, int y, int size, int[] answer) {
    if (flag(arr, x, y, size)) {
        answer[arr[x][y]] += 1;
        return;
    }
    int newSize = size / 2;
    zip(arr, x, y, newSize, answer);
    zip(arr, x, y + newSize, newSize, answer);
    zip(arr, x + newSize, y, newSize, answer);
    zip(arr, x + newSize, y+ newSize, newSize, answer);
}

---

📌solution 함수

해당 함수의 목적

• 전체 배열을 압축하고, 최종적으로 0과 1의 개수를 반환
• arr : 원본 배열

zip 함수를 호출하여 배열을 압축하고, 결과를 answer 배열에 기록

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

---

💻 최종 코드 💻

class Solution {
    public boolean flag(int[][] arr, int x, int y, int size) {
        int val = arr[x][y];
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (arr[i][j] != val) {
                    return false;
                }
            }
        }
        return true;
    }

    public void zip(int[][] arr, int x, int y, int size, int[] answer) {
        if (flag(arr, x, y, size)) {
            answer[arr[x][y]] += 1;
            return;
        }
        int newSize = size / 2;
        zip(arr, x, y, newSize, answer);
        zip(arr, x, y + newSize, newSize, answer);
        zip(arr, x + newSize, y, newSize, answer);
        zip(arr, x + newSize, y+ newSize, newSize, answer);
    }
    public int[] solution(int[][] arr) {
        int[] answer = new int[2];
        zip(arr, 0, 0, arr.length, answer);
        return answer;
    }

    public static void main(String[] args) {
        int[][] arr = {{1,1,1,1,1,1,1,1},{0,1,1,1,1,1,1,1},{0,0,0,0,1,1,1,1},{0,1,0,0,1,1,1,1},{0,0,0,0,0,0,1,1},{0,0,0,0,0,0,0,1},{0,0,0,0,1,0,0,1},{0,0,0,0,1,1,1,1}};

        Solution sol = new Solution();
        for (int i : sol.solution(arr)) {
            System.out.print(i + " ");
        }
    }
}

👏👏👏👏👏👏👏👏👏