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

programmers.co.kr/learn/courses/30/lessons/68936?language=java

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

문제 풀이 :

백준 2630번 색종이 만들기와 같은 문제 szcode.tistory.com/8

class Solution {
	static int n,zero = 0, one = 0;
	static int[][] map;
	public static int[] solution(int[][] arr) {
        int[] answer = new int[2];
        n = arr.length;
        map = new int[n][n];
        for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j] = arr[i][j];
			}
		}
        div(0,0,n);
        
        answer[0] = zero;
        answer[1] = one;
        
        return answer;
    }

	public static void div(int x, int y, int n) {
		int count = 0;
		//전체 영역이 1로 가득 차있는지 확인
		for (int i = x; i < x+n; i++) {
			for (int j = y; j < y+n; j++) {
				if(map[i][j] == 1) count++;
			}
		}
		if(count == 0) zero++; //압축, 모든 영역 0 이라면
		else if(count == n*n) one++; // 압축, 모든 영역 1이라면
		else {// 그렇지 않다면 분할
			div(x,y,n/2);
			div(x,y+n/2,n/2);
			div(x+n/2,y,n/2);
			div(x+n/2,y+n/2,n/2);
		}
	}
}