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

def solution(arr):
    answer = []
    
    def div_qun(x,y, n):
        if n == 1:
            answer.append(arr[x][y])
            return
        
        start = arr[x][y]
        
        for i in range(n):
            for j in range(n):
                if arr[x+i][y+j] != start:
                    next_n = n//2
                    div_qun(x, y, next_n)
                    div_qun(x, y+next_n, next_n)
                    div_qun(x+next_n, y, next_n)
                    div_qun(x+next_n, y+next_n, next_n)
                    return
        answer.append(start)
        return
    div_qun(0,0,len(arr))
    return [answer.count(0), answer.count(1)]

대표적인 분할 정복 알고리즘 문제

2중 for 문을 돌면서 처음과 다른 숫자가 있다면 재귀한다. 이때 4등분해서 재귀하는데 탐색 크기 n 값을 2로 나누고 시작 좌표를 위 코드처럼 나눠주면 4개의 구역에 대해 분할해서 다시 탐색하게 된다.

이렇게 분할하면서 진행하면서 0과 1에 대한 정보를 저장한 후

최종적으로 0, 1의 갯수를 세면 정답을 구할 수 있다.