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

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

🙋‍♂️ 들어가며

이번에는 분할정복 중 1개인 quad_tree에 대해 배워보자

쿼드 트리는 쪼갤 수 없을때까지 계속 쪼개어 문제를 해결하는 방식이다.

✅ 코드

class Solution {
    static int[] answer;
    
    
    public int[] solution(int[][] arr) {
        answer = new int[2];
        
        int sr = 0;
        int sc = 0;
        int N = arr.length;
        back_tracking(sr, sc, N, arr);
        return answer;
    }
    
    
    // back_tracking
    static void back_tracking(int r, int c, int cur_size, int[][] arr) {
        // 1. 첫 원소
        int first_val = arr[r][c];
        
        // 2. 검사
        if (is_all_same(first_val, r, c, cur_size, arr)) {
            answer[first_val]++;
            return;
        }
        
        
        // 3. 4방향 분할
        int new_size = cur_size / 2;
        
        // 3-1. 왼위
        back_tracking(r, c, new_size, arr);
        
        // 3-2. 오위
        back_tracking(r, c + new_size, new_size, arr);
        
        // 3-3. 왼아래
        back_tracking(r + new_size, c, new_size, arr);
        
        // 3-4. 오아래
        back_tracking(r + new_size, c + new_size, new_size, arr);
    }
    
    
    
    
    static boolean is_all_same(int first_val, int r, int c, int new_size, int[][] arr) {
        for (int i = r; i < r + new_size; i++) {
            for (int j = c; j < c + new_size; j++) {
                if (arr[i][j] != first_val) return false;
            }
        }
        return true;
    }
    
    
}