[프로그래머스] 68936번 : 쿼드 압축

이런식으로 0과 1로 정사각형 배열이 주어지면 1/4 씩 계속해서 탐색하면서 각 모든 값들이 0이나 1로 통일되는지 확인하고, 된다면 개수를 늘려주는 방식으로 구현하면 된다.

$2^n * 2^n$ 크기의 배열이며, n의 최대 크기는 10이기 때문에 dfs를 통한 완전 탐색으로 구현했다. 사실 완전 탐색을 해야 각 정사각형 안에 값들이 모두 같은지 확인 가능하기 때문에 완전 탐색은 필수인 듯 하다.

크게 어렵지는 않은 문제였지만, dfs를 통해 재귀적인 접근을 한 번 더 리마인드 하는 시간이였다.

class Solution {
    static int[] answer;
    public int[] solution(int[][] arr) {
        answer = new int[2]; // 0, 1
        
        dfs(arr, 0, 0, arr.length);
        
        return answer;
    }
    
    public void dfs(int[][] arr, int x, int y, int length) {
        if (zipCheck(arr, x, y, length, arr[x][y])) { // 압축 가능 여/부
            if (arr[x][y] == 0) {
                answer[0]++;
            } else {
                answer[1]++;
            }
            return;
        }
        
        
        // quard
        dfs(arr, x, y, length/2);
        dfs(arr, x, y + length/2, length/2);
        dfs(arr, x + length/2, y, length/2);
        dfs(arr, x + length/2, y + length/2, length/2);
    }
    
    public boolean zipCheck(int[][] arr, int x, int y, int length, int num) {
        for (int i=x; i<x + length; i++) {
            for (int j=y; j<y + length; j++) {
                if (arr[i][j] != num) {
                    return false;
                }
            }
        }
        return true;
    }
}