(Java) 프로그래머스 - 쿼드 압축 후 개수 세기

문제를 읽자마자 재귀를 활용해서 풀어야 한다는 사실을 알 수 있었다.

다만 로직을 한참을 고민했다.

재귀 탈출은 어떤 조건에서 해야 할지 어떤 상황에서 재귀 탐색이 들어갈지 기준을 잘 잡지 못했기 때문이다.

문제를 풀고나서 이 문제가 분할 정복에 속한다는 것을 알게 되었다.

지금까지 분할정복 문제를 한 번도 풀지 않아서 더 헤맸던 것 같다.

 

로직은 x, y 좌표를 기준으로 탐색 범위를 지정한다. 그리고 영역 분할 메서드를 호출한다.

그리고 현재 영역이 압축이 가능한지 압축 메서드를 호출하여 확인한다.

압축이 가능하다면 answer 배열에 바로 값을 업데이트 하고

압축이 불가능하다면 영역을 4개로 나누어서 재귀 호출을 진행한다.

1번 영역이 위 왼쪽, 2번 영역이 위 오른쪽, 3번 영역이 아래 왼쪽, 4번 영역이 아래 오른쪽이다.

size가 1까지 줄어들었다면 재귀 탈출문에 의해 answer 배열의 값이 증가한다.

---

최종 코드

class Solution {
    static int[] answer;
    public int[] solution(int[][] arr) {
        answer = new int[2];

        // 영역 분할 메서드 호출
        recursion(arr, 0, 0, arr.length);
        return answer;
    }
    // 영역 분할 메서드
    static void recursion(int[][] arr, int x, int y, int size) {
        // 현재 영역이 압축 가능하다면 answer 배열에 값 추가하고 반환
        if (compact(arr, x, y, size)) {
            answer[arr[x][y]]++;
            return;
        }
        // 1번 영역
        recursion(arr, x, y, size / 2);
        // 2번 영역
        recursion(arr, x + size / 2, y, size / 2);
        // 3번 영역
        recursion(arr, x, y + size / 2, size / 2);
        // 4번 영역
        recursion(arr, x + size / 2, y + size / 2, size / 2);
    }

    // 압축 가능한지 판단하는 메서드
    static boolean compact(int[][] arr, int x, int y, int size) {
        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;
    }
}