[Programmers] Lv2. 쿼드압축 후 개수 세기 Python 문제 풀이

문제

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

프로그래머스

 

어떻게 풀었는가

쿼드 트리 압축은 전형적인 분할 정복(Divide and Conquer) 문제다.

핵심 아이디어

영역 안의 모든 값이 같으면 하나로 압축하고, 아니면 4등분해서 각각 다시 확인한다. 이 과정을 재귀적으로 반복하면 된다.

구현 흐름

1. 현재 영역의 첫 번째 값(arr[x][y])을 기준으로 잡는다.
2. 영역 전체를 순회하면서 기준과 다른 값이 하나라도 발견되면, 즉시 4등분하여 재귀 호출한다. 이때 더 이상 탐색을 계속할 필요가 없으므로 바로 return한다.
3. 영역 전체가 같은 값이라면 해당 값의 카운트를 1 증가시킨다.

포인트는 다른 값을 발견하는 즉시 4분할로 넘어가는 것이다. 영역 전체를 다 확인한 뒤 분할하는 것보다 불필요한 탐색을 줄일 수 있다.

시간복잡도

배열 크기를 N×N이라 하면, 최악의 경우(체스판처럼 0과 1이 번갈아 나오는 경우) 모든 칸을 개별적으로 확인해야 하므로 O(N²log N)이다. 모든 값이 같은 최선의 경우에는 O(N²)에 끝난다.

 

코드

def solution(arr):
    count = [0, 0]

    def compress(x, y, size):
        first = arr[x][y]

        for i in range(x, x + size):
            for j in range(y, y + size):
                if arr[i][j] != first:
                    half = size // 2
                    compress(x, y, half)
                    compress(x, y + half, half)
                    compress(x + half, y, half)
                    compress(x + half, y + half, half)
                    return

        count[first] += 1

    compress(0, 0, len(arr))

    return count