9. 쿼드 압축 후 개수세기 JAVA (프로그래머스)

가. 문제파악

 1. 유형 : 분할정복, DFS

    -   예전에 한번 본적이 있는 문제라 쉽게 풀줄 알았는데 생각보다 어려웠다 ..

    -   어렴풋한 기억으로 풀려다보니 모든걸 쪼갠뒤에 답을 구하려하니 답이 나오지 않았다.

 

나. 코드 

 1. 풀이 : 4방면으로 쪼개자!

    -  스타트 지점이 중요한데 (0,0) 을 기준으로 큰 -> 작은 사각형 순으로 4방면으로 분할하자!

    -  4방면으로 분할하기 전에 압축할 수 있는지를 판단 해야한다!

          => 전부 1 또는 0이라면 하나로 압축이 가능하므로 큰거 부터 판단해야한다.

import java.util.Arrays;

public class Solution {

    public int[] solution(int[][] arr){
        ans = new int[2];
        div(0,0,arr.length,arr);
        return ans;
    }

    private static int[] ans;

    public void div(int x, int y, int len,int[][] arr){

        boolean isZero = true;
        boolean isOne = true;


        for (int i = x; i < x+len  ; i++) {
            for (int j = y; j <y+len; j++) {
                      if(arr[i][j] == 1) isZero = false;
                      if(arr[i][j] == 0) isOne= false;
            }
        }


        if(isOne){
            ans[1]++;
            return;
        }

        if(isZero){
            ans[0]++;
            return;
        }


        div(x,y,len/2,arr);
        div(x+len/2,y,len/2,arr);
        div(x,y+len/2,len/2,arr);
        div(x+len/2,y+len/2,len/2,arr);
    }

}

 

참고 : yabmoons.tistory.com/596