[프로그래머스] 쿼드 압축 후 개수 세기 (Java)

문제

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

코딩테스트 연습 - 쿼드압축 후 개수 세기

 

풀이

대표적인 분할 정복 문제로, 재귀 함수를 사용하여 작게 쪼개면서 푼다. 

아래와 백준 문제와 풀이가 동일하다.

2021.11.16 - [Problem Solving/BOJ] - [BOJ 2630] 색종이 만들기 (Java)

[BOJ 2630] 색종이 만들기 (Java)

 

소스코드

class Solution {
    public int oneCnt;
    public int zeroCnt;
    public int[] solution(int[][] arr) {
        int[] answer = {};
        
        oneCnt = 0;
        zeroCnt = 0;
        recur(arr, 0, 0, arr.length);
        
        return new int[]{zeroCnt, oneCnt};
    }
    
    public void recur(int[][] arr, int x, int y, int n){
        int tempOneCnt = 0;
        for(int i = x; i < x+n; i++){
            for(int j = y; j < y+n; j++){
                if(arr[i][j] == 1) tempOneCnt++;
            }
        }
        
        if(tempOneCnt == n*n){
            oneCnt++;
        } else if(tempOneCnt == 0){
            zeroCnt++;
        } else {
            recur(arr, x, y, n/2); // up-left
            recur(arr, x, y+n/2, n/2); // up-right
            recur(arr, x+n/2, y, n/2); // down-left
            recur(arr, x+n/2, y+n/2, n/2); // down-right
        }
        
    }
}