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

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

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

 

해결 방법 : 재귀

• 사각형의 가장 왼쪽 위 모서리 좌표와, 해당 정사각형 변의 길이를 기준으로 잡는다.
• 현재 정사각형이 압축 불가능하다면(다른 값이 존재), 4등분하여 재귀 호출한다.
  • 분할 된 정사각형의 좌표만 신경쓰면 됨.

def solution(arr):
    answer = {0 : 0, 1 : 0}
    
    def devide(row, col, l): # row, col, 현재 사각형 길이
        if l == 1: # 더 이상 분할 X
            answer[arr[row][col]] += 1
            return
        
        first = arr[row][col] # 첫번째 값
        for r in range(row, row + l):
            for c in range(col, col + l):
                if arr[r][c] != first: # 현재 사각형 압축 불가능 => 4분할
                    devide(row, col, l//2)
                    devide(row + l//2, col, l//2)
                    devide(row, col + l//2, l//2)
                    devide(row + l//2, col + l//2, l//2)
                    return # 분할은 한 번만 해야 하므로 return
        
        answer[first] += 1 # 압축 가능, 해당 숫자 ++
                    
    devide(0, 0, len(arr))
    
    return list(answer.values())