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

https://programmers.co.kr/learn/courses/30/lessons/68936

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

- 백준에 있는 쿼드트리 압축 문제와 거의 똑같은 문제다. 각 구간의 시작점과 길이를 생각하는 것이 포인트인데, 이 문제에서는 2의 거듭 제곱수 형태를 하고 있으므로 재귀 호출마다 length // = 2를 해주는 식으로 진행하면 된다.

- 각 구간에서 하나라도 다른 숫자가 있다면 그 영역을 4개로 쪼개서 재귀 호출을 하고 반복문을 탈출한다.

- 각 구간의 수가 모두 같다면 그 값을 1씩 더해준다.

def quadTree(arr, x, y, length, answer):
    start = arr[x][y]
    flag = True
    for i in range(x, x + length):
        for j in range(y, y + length):
            # 하나라도 다른 수가 있으면 4개로 쪼개서 재귀 호출
            if start != arr[i][j]:
                length //= 2
                quadTree(arr, x, y, length, answer)
                quadTree(arr, x, y + length, length, answer)
                quadTree(arr, x + length, y, length, answer)
                quadTree(arr, x + length, y + length, length, answer)
                flag = False
                break
        # 다르다면 반복문 탈출
        if not flag:
            break
    # 모든 수가 같다면 카운트해주기
    if flag:
        if start == 0: answer[0] += 1
        elif start == 1: answer[1] += 1

def solution(arr):
    answer = [0,0]
    quadTree(arr, 0, 0, len(arr), answer)
    return answer