프로그래머스 - 쿼드압축 후 개수 세기

쿼드압축 후 개수 세기 : https://school.programmers.co.kr/learn/courses/30/lessons/68936

---

Problem

---

Solve

주어진 2차원 배열에서 1,2,3,4 사분면으로 분리하여 해당 범위에 모두 동일한 값을 가지고 있다면 해당 값을 +1로 증가시키고 재귀를 중단합니다.
만약 모두 같은 값이 아니라면, 해당 범위를 다시 4등분으로 나누어 재귀를 수행하고 크기가 1일때까지 반복합니다.

	void recursive(int[][] arr, int range, int start, int end){
    	//범위의 크기가 1인 범위까지 확인했다면 재귀 종료
        if(range==0) return;
        
        //범위의 맨위 왼쪽의 좌표인 start,end부터 범위의 크기까지 동일한 값을 가지는지 확인합니다.
        if(isAllEquals(arr,range, start,end)){
        	//동일한 값을 가진다면 answer[범위의 동일한 값]을 증가시킵니다.
            answer[arr[start][end]]++;
        }
        //동일하지 않다면 4등분하여 재귀를 수행하여줍니다.
        else{
        	//1사분면
            recursive(arr, range/2, start, end);
            //2사분면
            recursive(arr, range/2, start, end+range/2);
            //3사분면
            recursive(arr, range/2, start+range/2, end);
            //4사분면
            recursive(arr, range/2, start+range/2, end+range/2);
        }
    }

---

Code

class Solution {
    int[] answer = new int[2];
    public int[] solution(int[][] arr) {
        int range = arr.length;
        
        recursive(arr, range, 0,0);
        
        return answer;
    }
    
    void recursive(int[][] arr, int range, int start, int end){
        if(range==0) return;
        
        if(isAllEquals(arr,range, start,end)){
            answer[arr[start][end]]++;
        }else{
            recursive(arr, range/2, start, end);
            recursive(arr, range/2, start, end+range/2);
            recursive(arr, range/2, start+range/2, end);
            recursive(arr, range/2, start+range/2, end+range/2);
        }
    }
    
    boolean isAllEquals(int[][] arr, int range, int start, int end){
        int pivot = arr[start][end];
        
        for(int i=start;i<start+range;i++){
            for(int j=end;j<end+range;j++){
                if(arr[i][j] != pivot){
                    return false;
                }
            }
        }
        return true;
    }
}

---

Result

---

Reference