프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간 초과 (제한 시간 이후 해결)

from collections import deque
from itertools import chain

def box_sum(box):

    return sum(list(chain(*box)))

def get_boxes(new_arr):

    length = len(new_arr[0])
    box1 = [subarr[:length//2] for subarr in new_arr[:length//2]]
    box2 = [subarr[:length//2] for subarr in new_arr[length//2:length]]
    box3 = [subarr[length//2:length] for subarr in new_arr[:length//2]]
    box4 = [subarr[length//2:length] for subarr in new_arr[length//2:length]]
    boxes = [box1, box2, box3, box4]
    
    return boxes

def solution(arr):
    answer = [0,0]
    
    arr_sum = box_sum(arr)
    if arr_sum==0:
        return [1,0]
    elif arr_sum==len(arr)**2:
        return [0,1]
    
    queue = deque([arr])
    
    while queue:
        
        new_arr = queue.popleft()
        boxes = get_boxes(new_arr)
        
        for box in boxes:
            length = len(box) 

            sum_box = box_sum(box)
            
            if box:
                if sum_box==0:
                    answer[0] += 1
                elif sum_box==length**2:
                    answer[1] += 1

                else:
                    queue.append(box)

    return answer

0과 1로 이루어진 행과 열의 길이가 2^n인 (정사각형) 2차원 배열(arr)이 주어질 때, 그림과 같이 '쿼드 트리 압축'을 통해 최종적으로 남는 0의 개수와 1의 개수를 구하는 문제입니다.🐇🐇🐇

Queue/BFS와 2중 리스트 모든 요소의 합을 구하는 알고리즘을 활용하여, 현재 배열을 정사각형 형태로 1/4씩 자르고 자른 정사각형들이 전부 0 혹은 1로 이루어졌는지 판단하였습니다.

만약 자른 정사각형의 요소들이 0 혹은 1로만 이루어졌다면 다음 Queue에 append 하지 않고 갯수를 1개 추가합니다. 만약 아니라면 자른 정사각형을 Queue에 append하여 다시 판단하는 과정입니다.

또한 0 혹은 1로만 이루어졌는지 확인하기 위해 'chain' 라이브러리를 활용하여,

from itertools import chain
sum(list(chain(*list1)))

2중 리스트 요소의 모든 합을 구하여 해결하였습니다.

[다른 사람의 풀이1]

cnt = [0, 0] 

def get_units(n):    
    zeros = [[0 for _ in range(n)] for _ in range(n)]    
    ones = [[1 for _ in range(n)] for _ in range(n)]    
    return zeros, ones 

def quad_zip(arr, n):    
    global cnt    
    
    # 바로 구성할 수 있는 경우    
    zeros, ones = get_units(n)    
    
    if arr == zeros:        
        cnt[0] += 1        
        return    
    elif arr == ones:        
        cnt[1] += 1        
        return    
    
    # 더 이상 쪼갤 수 없는 경우    
    if n == 2:        
        for nums in arr:            
            for num in nums:                
                if num == 0: 
                    cnt[0] += 1                
                else: 
                    cnt[1] += 1        
        return    
    
    # 쪼갤 수 있는 경우    
    zeros, ones = get_units(n // 2)    
    
    # 압축 가능한 지 확인    
    for i in range(0, n, n // 2):        
        for j in range(0, n, n // 2):            
            quad = [row[j : j + n // 2] for row in arr[i : i + n // 2]]            
            if quad == zeros:                
                cnt[0] += 1            
            elif quad == ones:                
                cnt[1] += 1            
            else: quad_zip(quad, len(quad))    
    return 
                
def solution(arr):    
    quad_zip(arr, len(arr))    
    return cnt

'나의 풀이'와 같이 현재 배열에서 1/4한 정사각형 형태로 잘라 확인하는 방식입니다.

이때, 자른 정사각형이 모두 0 혹은 1로 이루어져있는지 확인하기 위해 0으로만 이루어진 배열(zeros), 1로만 이루어진 배열(ones)을 직접 정의하고 비교했다는 점이 달랐습니다.🐹🐹🐹

[다른 사람의 풀이2]

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

    def comp(x, y, n):
        init = arr[x][y]  # 해당 네모값중 하나 # 모두 같아야 통과임
        for i in range(x, x + n):
            for j in range(y, y + n):
                if arr[i][j] != init:  # 한번이라도 다르면 그 네모는 압축불가
                    nn = n // 2
                    comp(x, y, nn)
                    comp(x, y + nn, nn)
                    comp(x + nn, y, nn)
                    comp(x + nn, y + nn, nn)
                    return

        # 무사히 다 통과했다면 압축가능
        answer[init] += 1

    comp(0, 0, N)
    return answer

가장 간결한 풀이였습니다.

먼저 현재 배열의 가장 첫번째 요소(init)를 정의합니다.🐳🐳🐳

만약 첫번째 요소를 제외한 요소들 중 만약 하나라도 다른 요소가 존재한다면

if arr[i][j] != init:  # 한번이라도 다르면 그 네모는 압축불가
	nn = n // 2
    comp(x, y, nn)
    comp(x, y + nn, nn)
    comp(x + nn, y, nn)
    comp(x + nn, y + nn, nn)
                    

1/4 크기로 자른 정사각형들(왼쪽 위, 왼쪽 아래, 오른쪽 위, 오른쪽 아래)을 재귀시켜 자른 정사각형별로 다시 판단합니다.

반대러, 모든 첫번째 요소(init)를 포함한 모든 요소가 같다면 갯수를 +1하여 현재 정사각형을 완료하는 방식입니다.

감사합니다.