[프로그래머스] 쿼드압축 후 개수 세기 - JAVA (월간 코드 챌린지 시즌1)

https://school.programmers.co.kr/learn/courses/30/lessons/68936

프로그래머스

 

한 변의 길이가 2^n 인 정사각형으로 주어지기 때문에, 정사각형 영역을 4등분 해가며 재귀 구현 

• 재귀함수의 매개변수 : arr배열, 시작위치 (x,y), 영역 한변의 길이
• 영역 안의 모든 값이 같은지 확인 후, 모두 같은 값이라면 answer[값] ++ 후 재귀 종료 
• 하나라도 다른 값이 있다면 4등분 하여 재귀 

 

class Solution {
    static int[] answer;
    private boolean isSame(int[][] arr, int x, int y, int len, int val){
        for(int i=x; i<x+len; i++){
            for(int j=y; j<y+len; j++){
                if(arr[i][j] != val) return false;
            }
        }
        return true; 
    }
    private void quad(int[][] arr, int x, int y, int len){
        //만약에 영역 안의 수가 모두다 같으면, 
        if(isSame(arr, x, y, len, arr[x][y])){
            answer[arr[x][y]]++;
            return; 
        }
        
        len/=2; 
        quad(arr, x, y, len); 
        quad(arr, x+len, y, len);
        quad(arr, x, y+len, len);
        quad(arr, x+len, y+len, len); 
    }
    public int[] solution(int[][] arr) {
        answer = new int[2]; 
        //매개변수 : 시작(x,y), 한변의 길이 
        quad(arr, 0,0, arr.length); 
        return answer;
    }
}