[알고리즘] 프로그래머스 - 쿼드 압축 후 개수세기 LV02 Java

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

프로그래머스

 

package Programmers;

public class 쿼드압축후개수세기 {
    public static void main(String[] args){
        쿼드압축후개수세기 T = new 쿼드압축후개수세기();
        int[][] arr = {{1,1,0,0},{1,0,0,0},{1,0,0,1},{1,1,1,1}};
        T.solution(arr);
    }

    static int[] answer = new int[2];
    public int[] solution(int[][] arr) {
        int totSize = arr.length;
        dq(0,0, totSize, arr);
        return answer;
    }

    public void dq(int stX, int stY, int size, int[][] arr){
        if(check(stX, stY, size, arr)){
            //arr[stX][stY] 가 0이거나 1일때 answer에 카운팅해준다.
            answer[arr[stX][stY]]++;
            return;
        }
        //2사분면
        dq(stX, stY, size / 2, arr);
        //1사분면
        dq(stX + size / 2, stY, size / 2, arr);
        //3사분면
        dq(stX, stY + size / 2, size / 2, arr);
        //4사분면
        dq(stX + size / 2, stY + size / 2, size / 2, arr);


    }



    public boolean check(int x, int y, int size, int[][] arr){
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if(arr[x][y] != arr[i][j]) return false;
            }
        }
        return true;
    }
}

1. 풀이 

 - 분할정복 알고리즘으로 접근 

 - 1사분면 ~ 4사분면으로 나누는 재귀

 - check 는 나눠진 사분면에서 하나라도 틀린게 있다면 false 반환한다. 

    check 가 참이면 나눠진 사분면안에 모든값들은 같은값이기 때문에 answer에 값을 더해준다.

- 사분면이 나눠지면 그안에서도 1~4분면까지 나눠지게 되고 계속 재귀로 푼다.

 

answer의 0번 인덱스는 0의 개수가 들어가고 

                 1번 인덱스는 1의 개수가 들어간다.

 ※ 참고

 

사분면

보기 편하게 사분면으로 주석달아놓음 1사분면은 11시방향이 아니라 1시방향부터 시계방향으로 4분면까지 있으니 참고