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

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

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

DFS를 이용해서 제일 작은 부분(길이가 1이 될 때)까지 쪼개가며 들어가야한다.

사각형을 절반씩 나누어 4개의 칸으로 만들면

시작점이 (0,0) (0, 0 + length/2), (0 + length/2,0),(0 + length/2,0 + length/2) 라는 것에서 착안하여

일반화를 위해 0대신에 row, col과 같은 값을 넣어주면 된다.

검증은 for문 돌려서 맞으면 zero나 one을 증가해주는 방식!

import java.util.*;
class Solution {
	static int one, zero;
    public int[] solution(int[][] arr) {
        int[] answer = new int[2];
        dfs(arr, arr.length,0,0);

        answer[0] = zero;
        answer[1] = one;
        return answer;
    }
    
    public static void dfs(int[][] arr, int length, int row, int col) {
    	if(length == 1) {
    		if(arr[row][col] == 1) one++;
    		else zero++;
    		return;
    	}
    	
    	if(same(arr, row, col, length)) return;
    	
    	length /=2;
    	//4방면으로 검증
    	dfs(arr, length, row, col);
    	dfs(arr, length, row+length, col);
    	dfs(arr, length, row, col+length);
    	dfs(arr, length, row+length, col+length);	
    }
    
    //같은지 확인하는 부분.
    public static boolean same(int[][] arr, int row, int col, int length) {
    	int target = arr[row][col];
    	for(int i = row; i<row+length; i++) {
    		for (int j = col; j < col+length; j++) {
				if(target != arr[i][j]) return false;
			}
    	}
    	if(target == 1) one++;
    	else zero++;
    return true;	
    }
}