쿼드압축 후 개수 세기

작성일: 2024-10-24

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/68936

접근 방식

• 분할정복 알고리즘을 통해 각 사분면을 사분면으로 계속 쪼갬. 만약 해당 사분면이 0혹은 1로만 이루어졌다면 해당 숫자 +1

학습

분할 정복 알고리즘에 대해서는 알지 못했기에 답을 보고 이해하면서 해결하려고 노력함.

이후 분할 정복 알고리즘 문제를 몇 개 더 풀면서 감을 잡을 예정.

결과

소스 코드

class Solution {
    static int answer[] = new int[2];

    public int[] solution(int[][] arr) {
        int n = arr.length;
        tree(arr, n, 0, 0);
        return answer;
    }

    private void tree(int[][] arr, int n, int x, int y){
        if(check(arr, x, y, n)){
            answer[arr[x][y]]++;
            return;
        }

        tree(arr, n/2, x, y); // 1사분면
        tree(arr, n/2, x+n/2, y); // 2사분면
        tree(arr, n/2, x, y+n/2); // 3사분면
        tree(arr, n/2, x+n/2, y+n/2); // 4사분면
    }


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

다른 접근 방식

없음.

알게 된 점

분할 정복 알고리즘을 통해, 주어진 배열을 사분면으로 나눠서 검사를 할 수 있음.

재귀 함수를 이용하여, 각 분면별로 계속 반으로 나눔.

재귀를 돌 때마다, check 함수 실행.

만약 해당 분면이 모두 0 or 1로 이루어졌다면 true를 반환해서 해당 수를 +1하고 리턴
=> 이루어져있지 않았다면(다른 숫자가 석여있기에, 좀 더 들어가야 함. 압축 불가), 게속 사분면을 쪼갬