[Swift] 쿼드압축 후 개수세기

import Foundation

func solution(_ arr:[[Int]]) -> [Int] {
    var zeroCount = 0
    var oneCount = 0

    func quadCompression(_ row: Int, _ col: Int, _ n: Int) {
        let target = arr[row][col]
        
        for i in row..<row+n {
            for j in col..<col+n {
                if target != arr[i][j] {
                    quadCompression(row, col, n/2)
                    quadCompression(row, col + n/2, n/2)
                    quadCompression(row + n/2, col, n/2)
                    quadCompression(row + n/2, col + n/2, n/2)
                    return
                }
            }
        }
        
        if target == 0 { zeroCount += 1}
        else  { oneCount += 1 }
    }
    
    quadCompression(0, 0, arr.count)
    
    return [zeroCount, oneCount]
}

 

(0,0)을 기준으로 n * n 배열일때는 아래와 같이 나눌 수 있다.

 

그렇다면 (x,y)가 기준일 때는 아래와 같이 나눌 수 있다.

 

n = 4일때를 예로 들면 전체가 다 같은지 확인한 뒤 아니라면 아래와 같이 네부분으로 나누고

네부분을 나눈것을 확인한뒤 일치하지 않는다면

 

아래와 같이 나눌 수 있다.

 

 

위 사진들을 보면  기준이되는 가장 왼쪽의 최상단 값들은 고정이고 배열의 크기 N이 점점 줄어드는것을 확인할 수 있다.

 

재귀함수 정의

1)  N * N 크기의 배열일때 arr[x][y]값과 나머지 값들이 같지 않다면

1-2) (x,y) (x, y + n/2), (x + n/2, y) (x + n/2, y + n/2) 를 각 기준으로 크기가 N/2 * N/2 크기의배열로 나누어 주고  각 기준점을 기준으로 1로 돌아간다.

2) 만약 같다면 결과값에 더해주고 끝낸다.