프로그래머스 쿼드압축 후 개수세기

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

0과 1로 이루어진 이차원 배열을 쿼드압축한 후 0과 1의 개수를 구하는 문제이다.

위 예시처럼, 칸을 분할하여 모두 0이거나 모두 1인 경우 하나의 숫자로 합칠 수 있다.

가능한 한 합친 뒤에 0과 1의 개수를 세는 문제이다.

만약 주어진 이차원 배열이 모두 1이라면, 분할할 필요 없이 전체를 합친 후 (0, 1)을 반환하면 된다.

따라서 바깥 사각형을 모두 확인한 뒤, 0과 1이 섞여 있다면 그 때 절반 크기로 4분할하면 될 것 같다고 생각했다.

풀이 방법을 예시를 통해 나타내면 아래와 같다.

먼저 크기만큼의 가장 바깥 정사각형 범위가 모두 같은 숫자인지 확인한다.

모두 같은숫자가 아니므로, 크기 / 2로 4분할해 각각 확인한다.

4분할 후, 오른쪽 아래를 제외한 3 지역이 모두 같은 숫자이다.
따라서 0을 2개, 1을 1개 증가시킨다.

이후 오른쪽 아래 분면에 대해 다시 크기 / 2로 4분할해 각각 확인한다.

0을 1개, 1을 3개 증가시킨다.

class Solution {
    fun solution(arr: Array<IntArray>): IntArray {
        val zeroOne = intArrayOf(0, 0)

        fun dfs(r: Int, c: Int, sz: Int){
            val zipable = canZip(arr, r, c, sz)
            if(zipable != -1){
                zeroOne[zipable]++
                return
            }

            dfs(r, c, sz / 2)
            dfs(r, c + sz / 2, sz / 2)
            dfs(r + sz / 2, c, sz / 2)
            dfs(r + sz / 2, c + sz / 2, sz / 2)
        }

        dfs(0, 0, arr.size)

        return zeroOne
    }

    fun canZip(arr: Array<IntArray>, r: Int, c: Int, sz: Int): Int{
        val start = arr[r][c]
        for(i in r until r + sz){
            for(j in c until c + sz){
                if(arr[i][j] != start) return -1
            }
        }
        return start
    }
}

편의를 위해 zeroOne이라는 크기 2짜리 IntArray를 생성해 0번 인덱스엔 0의 개수를, 1번 인덱스엔 1의 개수를 다루도록 하였다.

canZip이라는 함수를 만들어, 특정 위치부터 sz크기의 사각형 범위가 모두 같은 숫자인지 확인하였다.
+) 같은 숫자라면 그 숫자를, 다르다면 -1을 반환하게 해서 zeroOne의 인덱스를 증가시키기 편하도록 하였다.