[ Lv 2 ] 쿼드압축 후 개수 세기

풀이 과정

---

1. 현재 검사하려는 영역을 검사한다.

2. 현재 검사하려는 영역이 압축이 되지 않는다면 영역을 왼쪽위, 왼쪽아래, 오른쪽아래, 오른쪽 위로 4개 분할하여 재귀함수를 호출한다.

3. 영역의 크기가 1x1인 경우에는 하나의 영역으로 간주하고 종료

4. 영역이 압축이 된다면 무슨 영역인지 카운팅 해주고 종료

---

import sys

count = [0, 0]

sys.setrecursionlimit(10**6)

def check(arr, x1, y1, x2, y2):
    t = arr[x1][y1]
    for i in range(x1, x2+1):
        for j in range(y1, y2+1):
            if arr[i][j] != t:
                return False

    return True

def f(arr, x1, y1, x2, y2):
    if check(arr, x1, y1, x2, y2):
        t1 = arr[x1][y1]
        count[t1] += 1
        return

    if x1 == x2 and y1 == y2:
        count[arr[x1][y1]] += 1
        return

    midX = (x1 + x2) // 2
    midY = (y1 + y2) // 2

    f(arr, x1, y1, midX, midY) # 왼위
    f(arr, midX+1, y1, x2, midY) # 왼아
    f(arr, midX+1, midY+1, x2, y2) # 오아
    f(arr, x1, midY+1, midX, y2) # 오위

def solution(arr):
    answer = []
    t = len(arr)
    f(arr, 0, 0, t-1, t-1)
    return count

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges