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

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

프로그래머스

---

💡 접근 방법

이차원 배열 arr가 주어지고 쿼드 트리와 같은 방식으로 압축을 하는 문제이다.

출처 : 프로그래머스

여기서 포인트가 있는데 arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다.

처음부터 n개의 숫자를 합칠 수 있는지 확인하고 안 될 경우 n /2 그다음 n/2^2 이런 식으로 점점 줄여서 탐색을 시작하면 된다.

 

백트레킹을 사용해서 문제를 구현하고 탈출 조건으로는 check메서드를 통해서 해당칸이 전부 같은 숫자인지 검증을 해준다.

if (check(row, col, size)) {
    if (array[row][col] == 0) zero++;
    else one++;
    return;
}

private boolean check(int row, int col, int size) {
    int target = array[row][col];

    for (int i = row; i < row + size; i++) {
        for (int j = col; j < col + size; j++) {
            if (target != array[i][j]) return false;
        }
    }

    return true;
}

 

그다음 재귀로 돌려야 할부분을 생각을 해야 하는데 위의 포인트 2의 거듭 제곱수 형태를 하고 있기 때문에 n/2를 기준으로 하면 된다.

출처 : 프로그래머스

위의 순서를 기준으로 탐색을 할 때 전체 4 * 4가 똑같은 숫자인지 검증을 한다. 하지만 같은 수가 아니므로 2 * 2를 기준으로 탐색을 해야 한다.

왼쪽 아래(0, 0), 오른쪽 아래(0, 2), 왼쪽 위(2, 0), 오른쪽 위(2, 2)를 기준으로 다시 탐색을 한다. 그렇게 오른쪽 위(2, 2)가 모두 같은 수이므로 탈출조건을 완성하게 돼서 0의 숫자를 카운팅 해주고 탈출한다. 이런 식으로 1 * 1까지 탐색을 하고 점점 2를 나누면서 줄여 나가면 된다. 

int sliceSize = size / 2;

backtracking(row, col, sliceSize);
backtracking(row, col + sliceSize, sliceSize);
backtracking(row + sliceSize, col, sliceSize);
backtracking(row + sliceSize, col + sliceSize, sliceSize);

2 * 2 탐색

---

🗝 풀이 코드

class Solution {
    int zero = 0, one = 0;
    static int[][] array;

    public int[] solution(int[][] arr) {
        array = arr.clone();
        backtracking(0, 0, arr.length);

        return new int[]{zero, one};
    }

    private void backtracking(int row, int col, int size) {
        if (check(row, col, size)) {
            if (array[row][col] == 0) zero++;
            else one++;
            return;
        }

        int sliceSize = size / 2;

        backtracking(row, col, sliceSize);
        backtracking(row, col + sliceSize, sliceSize);
        backtracking(row + sliceSize, col, sliceSize);
        backtracking(row + sliceSize, col + sliceSize, sliceSize);
    }

    private boolean check(int row, int col, int size) {
        int target = array[row][col];

        for (int i = row; i < row + size; i++) {
            for (int j = col; j < col + size; j++) {
                if (target != array[i][j]) return false;
            }
        }

        return true;
    }
}