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

코딩테스트 연습 - 쿼드압축 후 개수 세기

풀이

분할정복 문제이다.

1. 각 사각형 안에서의 첫 좌표 값을 초기값으로 잡고, 

2. 범위를 2를 나눈 만큼 찾아 들어간다.

 

def solution(arr):
    answer = [0, 0]
    N = len(arr)
    
    def d_q(r, c, n):
        init = arr[r][c]
        for i in range(r, r + n):
            for j in range(c, c + n):
                if arr[i][j] != init:
                    nn = n // 2
                    d_q(r, c, nn)
                    d_q(r, c + nn, nn)
                    d_q(r + nn, c, nn)
                    d_q(r + nn, c + nn, nn)
                    return
                
        answer[init] += 1
    
    d_q(0, 0, N)
    return answer