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

문제

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

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

풀이

압축하고자하는 특정 영역 S는 (시작 행 r1, 시작 열 c1, 사각형 한 변의 길이 s)로 표시한다.

 

1. 영역 S내의 모든 원소가 0이거나 1인지 확인한다.

check = sum([arr[i][j] for i in range(r1, r1 + s) for j in range(c1, c1 + s)])
"""
모든 원소가 0이라면 check값은 0이고, 모든 원소가 1이라면 check값은 원소의 개수(s**2)와 같다.
"""

 

2. 

영역 S내의 모든 원소가 0이거나 1이라면,

S 내부의 0의 개수와 1의 개수를 answer에 반영한다.

 

3.

영역 S 내의 모든 원소가 0이거나 1이 아니라면(같은 값이 아니라면),

영역 S를 4개로 나눈다.

코드

def solution(arr):
    answer = [0, 0] # 0과 1의 개수를 저장하는 변수

    def conquer(r1, c1, s) :
    	# arr의 모든 원소가 0또는 1인지 확인하는 값
        check = sum([arr[i][j] for i in range(r1, r1 + s) for j in range(c1, c1 + s)])

        if check in [0, s**2] : # 사각형의 크기가 1이거나, 모든 원소가 0이거나 1일 때
        	answer[arr[r1][c1]==1] += 1
        else :
            s = int(s/2) # 1/4로 나눈 사각형 한 변의 크기
            rm, cm = r1+s, c1+s # 사각형 중점의 위치
            start_points = [(r1, c1), (r1, cm), (rm, cm), (rm, c1)] # 각 사각형의 시작 위치
            for r, c in start_point : 
            	conquer(r, c, s)

    conquer(0, 0, len(arr))
    return answer