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

문제 링크

---

프로그래머스

접근 방법

---

주어진 2차원 배열을 하나의 정사각형 영역으로 보고, 현재 영역이 모두 같은 값으로 이루어져 있는지 확인합니다.
만약 현재 영역 안에 다른 값이 섞여 있다면 영역을 4개의 정사각형으로 나누고, 각 영역에 대해 같은 과정을 재귀적으로 반복합니다.

소스 코드

---

class Solution {
    int[] cnt = {0, 0};
    int[][] board;

    void recursive(int y, int x, int size) {
        if (size == 1) {
            cnt[board[y][x]]++;
            return;
        }

        int value = board[y][x];
        boolean isSame = true;

        for (int i = y; i < y + size; i++) {
            for (int j = x; j < x + size; j++) {
                if (value != board[i][j]) {
                    isSame = false;
                    break;
                }
            }

            if (!isSame) {
                break;
            }
        }

        if (isSame) {
            cnt[value]++;
            return;
        }

        int half = size / 2;

        recursive(y, x, half);
        recursive(y + half, x, half);
        recursive(y, x + half, half);
        recursive(y + half, x + half, half);
    }

    public int[] solution(int[][] arr) {
        board = arr;
        recursive(0, 0, arr.length);
        return cnt;
    }
}

코드 설명

---

cnt 배열은 압축 후 남는 0과 1의 개수를 저장합니다.
cnt[0]에는 0의 개수가 저장되고, cnt[1]에는 1의 개수가 저장됩니다.

board에는 입력으로 받은 2차원 배열을 저장합니다.

recursive() 함수는 현재 확인할 정사각형 영역의 시작 좌표와 크기를 매개변수로 받습니다.
y와 x는 현재 영역의 왼쪽 위 좌표이고, size는 현재 영역의 한 변의 길이입니다.

size가 1이면 더 이상 나눌 수 없는 한 칸짜리 영역입니다.
따라서 해당 위치의 값이 0이면 cnt[0]을 증가시키고, 1이면 cnt[1]을 증가시킨 뒤 종료합니다.

 

현재 영역에 0과 1이 섞여 있다면 영역을 4등분해야 합니다.
half에 현재 크기의 절반을 저장한 뒤, 왼쪽 위, 왼쪽 아래, 오른쪽 위, 오른쪽 아래 영역을 차례대로 재귀 호출합니다.

solution() 함수에서는 입력 배열을 board에 저장하고, 전체 배열을 하나의 영역으로 보아 recursive(0, 0, arr.length)를 호출합니다.