프로그래머스 쿼드압축 후 개수 세기 파이썬

문제 링크

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

풀이

먼저, 이차원배열을 배열로 변환한다.

그  후 dfs를 이용하여 탐색한다.

 

minimize 압축함수 (=dfs함수)

i)

arr의 전체 원소가 모두 0이거나 1이면

그 원소에 해당하는 개수를 1 더해준다.

 

ii)

arr의 원소가 4이면

0의 갯수, 1의 갯수를 각각 더해준다.

 

i),ii)에 해당하지 않는 경우

arr을 4개 영역으로 분리한다.

그리고 4개의 영역을 각각 탐색한다.

 

 

 

전체 코드

def solution(arr):
    def minimize(arr):
        n = len(arr)
        if arr.count(arr[0]) == n:
            ans[arr[0]] += 1
            return

        if n == 4:
            ans[0] += arr.count(0)
            ans[1] += arr.count(1)
            return                                      
        
        arr1 = []
        arr2 = []
        arr3 = []
        arr4 = []
        m = int(n ** (1/2))
        
        
        for i in range(n):
            if i < n//2:
                if i % m < m // 2:
                    arr1.append(arr[i])
                else:
                    arr2.append(arr[i])
            else:
                if i % m < m // 2:
                    arr3.append(arr[i])
                else:
                    arr4.append(arr[i])

        minimize(arr1)
        minimize(arr2)
        minimize(arr3)
        minimize(arr4)
        
    ans = [0,0]
    if len(arr) == 1:
        ans[arr[0][0]] = 1
        return ans
    
    arrx = []
    n = len(arr)
    for i in range(n):
        for j in range(n):
            arrx.append(arr[i][j])
    
    minimize(arrx)
    
    return ans