쿼드압축 후 개수 세기 (lv2)

문제 설명

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
  • arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
  • arr의 각 행에 있는 모든 값은 0 또는 1 입니다.

---

 좀만 더 생각해봤으면 재귀함수로 접근가능하단것을 생각해낼 수 있었을텐데, BFS와 쿼드트리 구현으로 풀어버렸다... 큰 구조는 BFS로 행렬을 넣어주고, 꺼내서 원소가 모두 같다면 해당 원소의 개수에 +1을 해주고, 만약에 같지 않다면 4개의 행렬로 쪼개서 큐에 넣어주는 것이다. Quadtree 클래스는 행렬을 4개의 행렬로 쪼개서 반환해주며, 모두 같은 원소를 지닌 행렬은 '압축' 한다. 코딩을 앱개발로 입문했다보니 "구현"하는 쪽으로 접근하는데 너무 익숙해져버린듯 하다...

from math import ceil
from collections import deque

class Quadtree:
    def __init__(self,length):
        self.length = length
        self.quadtree = {i : {'values':set(), 'ary':[[] for _ in range(length)]} for i in range(4)}
        
    def push(self,row,col,value):
        key = self.coor_to_key(row,col)
        self.quadtree[key]['values'].add(value)
        self.quadtree[key]['ary'][row%self.length].append(value)
        
    def coor_to_key(self,row,col):
        return (row//self.length)*2 + (col//self.length)
    
    def compress(self):
        for i in range(4):
            if len(self.quadtree[i]['values']) == 1:
                self.quadtree[i]['ary'] = list(self.quadtree[i]['values'])
    
    def get(self):
        self.compress()
        return map(lambda x : x['ary'], self.quadtree.values())

def solution(arr):
    answer = [0,0]
    q = deque()
    q.append(arr)
    while q:
        mat = q.popleft()
        n = len(mat)
        quadtree = Quadtree(n//2)
        flag = True
        for row in range(n):
            for col in range(n):
                if flag and mat[row][col] != mat[0][0]:
                    flag = False
                quadtree.push(row,col,mat[row][col])
        if flag:
            answer[mat[0][0]] += 1
            continue
        for new_mat in quadtree.get():
            if len(new_mat) == 1:
                answer[new_mat[0]] += 1
            else:
                q.append(new_mat)
            
    return answer

 사실 이 모든건 재귀함수로 구현 가능한데, (0,0) 부터 (n,n)까지 원소가 다른게 있는지 검사하며 재귀적으로 (0,0)부터 (n//2,n//2), (0,n//2)부터 (n//2,n//2), (n//2,0)부터 (n//2,n) 과 같이 순회하는 것이다. 만약 원소가 모두 같다면 재귀함수는 호출되지 않으므로, 해당 원소 개수에 +1 을 해준다. 아래 링크를 참조했다.

[프로그래머스/파이썬] Level 2 쿼드압축 후 개수 세기 (velog.io)

[프로그래머스/파이썬] Level 2 쿼드압축 후 개수 세기

def solution(arr):
    result=[0,0]
    length=len(arr)
    
    def compression(a,b,l):
        start=arr[a][b]
        for i in range(a,a+l):
            for j in range(b,b+l):
                if arr[i][j]!=start:
                    l=l//2
                    compression(a,b,l)
                    compression(a,b+l,l)
                    compression(a+l,b,l)
                    compression(a+l,b+l,l)
                    return
                
        result[start]+=1
        
    compression(0,0,length)
    
    return (result)