프로그래머스 - 퀴드압축 후 개수 세기 문제 (자바)

programmers.co.kr/learn/courses/30/lessons/68936#

코딩테스트 연습 - 쿼드압축 후 개수 세기

재귀를 통해서 결정되는 0, 1의 수를 세면서 문제를 풀었다.

2의 배수인 정사각형을 주기 때문에 행렬의 길이가 동일하고 2로 나누어진다.

현재가 나누어질수 없는 크기라면(한칸) -> 해당 칸의 값의 개수를 +1

만약 행과 열의 n의 범위의 값이 같으면 해당 값 +1을 한번만 반영

만약 다르다면 왼쪽 위, 왼쪽 아래, 오른쪽 위, 오른쪽 아래를 다 재귀를 돌려준다. 

// 프로그래머스 퀴드압축 후 개수 세기 문제
class QuadImpress {
    private static int[] answer;

    private static void dfs(int n, int x, int y, int[][] arr) {
        if (n == 1) {
            answer[arr[x][y]]++;
            return;
        }
        if (isSame(n, x, y, arr)) {
            return;
        }

        dfs(n / 2, x, y, arr);
        dfs(n / 2, x + n / 2, y, arr);
        dfs(n / 2, x, y + n / 2, arr);
        dfs(n / 2, x + n / 2, y + n / 2, arr);
    }

    public static boolean isSame(int n, int x, int y, int[][] arr) {
        int temp = arr[x][y];
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (temp != arr[i][j]) {
                    return false;
                }
            }
        }
        answer[temp]++;
        return true;
    }

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