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

1. 문제

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

2. 풀이

재귀를 활용하는 것인데 꽤 어려웠다.
참고풀이
해당 풀이 링크를 통해서 해결하였다.

✨재귀에서 중요한 것은 3단계이다.

• 1. 상태
• 2. 종료 조건
• 3. 점화식

1. 상태

   (0, 0)에서 시작하여 가로길이와 세로길이가 size인 정사각형 탐색 후 → 4개로 쪼개가며 0과 1의 개수를 구한다.

           quad(arr, x, y, size/2);
           quad(arr, x+size/2, y, size/2);
           quad(arr, x, y+size/2, size/2);
           quad(arr, x+size/2, y+size/2, size/2);
   

2. 종료 조건

   범위 안 원소들이 모두 0이거나 1이면 정사각형을 더는 나누지 않는다.

3. 점화식

   quad(arr, x, y, size) = quad(arr, x, y, size/2);
   + quad(arr, x+size/2, y, size/2);
   + quad(arr, x, y+size/2, size/2);
   + quad(arr, x+size/2, y+size/2, size/2);

3. 전체코드

class Solution {
    int[] answer = new int[2];
    
    public int[] solution(int[][] arr) {
        quad(arr, 0, 0, arr.length);
        return answer;
    }
    
    public void quad(int[][] arr, int x, int y, int size){
        if( zip(arr, x, y, size, arr[x][y]) ){
            if(arr[x][y] == 1){
                answer[1] += 1;
            } else{
                answer[0] +=1 ;
            }
            return;
        }
        
        quad(arr, x, y, size/2);
        quad(arr, x+size/2, y, size/2);
        quad(arr, x, y+size/2, size/2);
        quad(arr, x+size/2, y+size/2, size/2);
    }
    
    public boolean zip(int[][] arr, int x, int y, int size, int val){
        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;
    }
}