쿼드압축 후 개수 세기 [자바]

 

🧫 문제 분석

✔️ 출처

쿼드압축 후 개수 세기 level 2

📖 문제

 

분할 정복 문제

 

처음은 전체를 다 돌아본다.

 

for문으로 주어진 영역이 모두 같은 수 인지 확인

 

아니라면 4등분으로 영역을 나눠서 각각 영역별로 재호출

영역 길이 / 2 한 값으로 4등분한다. 여기서는 행의 길이가 영역을 정한다.

 

비슷한 문제 포스팅

 

백준 1074번 : Z

백준 1030번 : 프렉탈 평면

백준 2447번 : 별 찍기 - 10

백준 2448번 : 별 찍기 - 11

---

🔅 문제 풀이

class Solution {
    // 분할 정복
    // for문으로 해당 영역 탐색
    int[] count = new int[2];
    
    public int[] solution(int[][] arr) {
        divAndConquer(0,0,arr.length,arr);
        return count;
    }
    
    private void divAndConquer(int r, int c, int size, int[][] arr) {
        
        //S 내부의 모든 수가 같은지 확인용
        if (areaSearch(r,c,size,arr)) {
            int firstIdx = arr[r][c];
            count[firstIdx]++;
            return;
        }
        
        int div = size / 2; // 반으로 나눈다. 
        divAndConquer(r,c + div, div, arr);       // 1사분면
        divAndConquer(r, c, div, arr);            // 2사분면
        divAndConquer(r + div, c, div, arr);      // 3사분면
        divAndConquer(r + div, c + div, div,arr); // 4사분면
    }
    
    private boolean areaSearch(int r, int c, int size, int[][] target) {
        for (int i = r; i < r + size; i++) {
            for (int j = c; j < c+ size; j++) {
                // 하나라도 다르다면 이영역은 4등분해야함
                if (target[r][c] != target[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}

❗ 오답노트 / 필요한 지식

1. 한 번이라도 풀어봤으면 매우 쉬운 문제