쿼드압축 후 개수 세기와 재귀함수

입출력 예시

[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] => [4, 9]
2차원 array를 input으로 받아서 압축 후 1과 0의 개수를 return함.

진짜 별로 보고 싶지 않은 문제다. 다시 풀라하면 좀 자신이 없다 하하

나의 풀이

def solution(arr):
    N = len(arr)
    answer = [0, 0]
    # 모든 원소가 1인지 확인
    is_all_ones = all(all(x == 1 for x in row) for row in arr)

    # 모든 원소가 0인지 확인
    is_all_zeros = all(all(x == 0 for x in row) for row in arr)

    
    if N == 2 or is_all_ones or is_all_zeros:
        if is_all_ones or is_all_zeros:
            if arr[0][0] == 0:
                answer = [1, 0]
            else:
                answer = [0, 1]
        
        elif N == 2 :
            count_0 = sum(row.count(0) for row in arr)
            count_1 = sum(row.count(1) for row in arr)
            answer = [count_0, count_1]
                
        return answer

    
    while not is_all_ones and not is_all_zeros:
        count_0 = sum(row.count(0) for row in arr)
        count_1 = sum(row.count(1) for row in arr)

        top_left = [arr[i][:N//2] for i in range(N//2)]
        bottom_left = [arr[i][:N//2] for i in range(N//2, N)]
        top_right = [arr[i][N//2:] for i in range(N//2)]
        bottom_right = [arr[i][N//2:] for i in range(N//2, N)]

        answer1 = solution(top_left)
        answer2 = solution(bottom_left)
        answer3 = solution(top_right)
        answer4 = solution(bottom_right)

        answer[0] = answer1[0] + answer2[0] + answer3[0] + answer4[0]
        answer[1] = answer1[1] + answer2[1] + answer3[1] + answer4[1]
    
        return answer

재귀함수는 두 부분으로 나눌 수 있다.

---

1. 가장 작은 단위를 어떻게 처리할 것인가?
2. 큰 단위를 작은 단위로 어떻게 쪼갤 것인가?

---

1. 이 문제에서는 n = 2, 즉 2*2 정사각형일 때가 제일 작은 단위이다. 그래서 2*2 정사각형이면 더 이상 쪼갤 필요도 없이 0으로만 이루어져 있는지 1로만 이루어져 있는지, 그렇지 않다면 0과 1의 개수를 세주어야 한다.

2. 쿼드 압축이라는 문제에 걸맞게, 4분할하여 함수를 재귀적으로 호출해준다. 각각 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 나누고 4분할한 답들을 모두 더하면 된다.

글로 쓰고 나니 엄청나게 간단하다. 그러나 너무너무 어려웠다.