[프로그래머스] Lv.2 쿼드압축 후 개수 세기 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/68936
• 🔑 분할정복 알고리즘, divide and conquer algorithm
  
  • 정사각형이 1칸짜리가 될 때까지 or 모두 같은 숫자의 정사각형이 나올 때까지 4등분 한다
  • 위 조건을 만족하면 정답에 숫자를 올려준다.
  • 모두 압축이 될 때까지 반복한다.

 

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

    def div(x, y, length):
        if length == 1:             # 1칸짜리 정사각형이 되면
            answer[arr[x][y]] += 1  # 정답에 정사각형 숫자 갯수 올림
            return
                
        t = arr[x][y]               # 시작 위치의 값 저장
        sw = 0
        for i in range(x, x + length):
            for j in range(y, y + length):
                if arr[i][j] != t:          # 시작 위치의 값과 다르면
                    sw = 1                      
                    break                   # 끝내기
            if sw:
                break
        if not sw:                          # 시작 위치의 값과 정사각형 안의 값이 다 같으면
            answer[t] += 1                  # 정답에 정사각형 숫자 갯수 올림
            return
    
        div(x, y, length // 2)                              # 4등분 했을 때 왼쪽 위
        div(x, y + length // 2, length // 2)                # 4등분 했을 때 오른쪽 위
        div(x+ length // 2, y, length // 2)                 # 4등분 했을 때 왼쪽 아래
        div(x+ length // 2, y + length // 2, length // 2)   # 4등분 했을 때 오른쪽 아래
    
    div(0, 0, length)  # x, y, 정사각형 길이
    
    return answer