[Programmers] 쿼드압축 후 개수 세기 - 월간 코드 챌린지1 (python)

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

쿼드압축 후 개수 세기

• 분할정복 방법으로 접근한다.

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

비슷한 문제로 백준 1992 - 쿼드트리를 들 수 있다.