[Level 2] 쿼드압축 후 개수 세기

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

코딩테스트 연습 - 쿼드압축 후 개수 세기

---

접근

쿼드 트리를 구현해보았다. 만약 행과 열의 개수가 같은 2차원 리스트에서 행의 개수가 4라고 가정해보자.

(0, 0)부터 시작해서 4x4를 모두 탐색했을 때 같은 숫자로 구성되어있지 않을 때는 4등분을 하면된다. 4등분을 했을 때 각각의 시작 위치를 파악하면 쉬운 문제였다. 

 

구현

- 아래의 함수를 통해 쿼드 트리를 구현하였다.

- 만약 n이 1일 때는 더 이상 나누지 못하기 때문에 현재 위치의 숫자를 카운트하고 return한다.

- 그렇지 않을 때는 범위 내의 숫자들이 모두 같은지 판단한다.

- 같다면 더 이상 나누지 않아도되지만 다를 때는 4등분을 해야한다.

- 결국 쿼드 트리를 몇 번 수행하는지 수행했을 때 해당된 숫자를 카운트하면 된다.

def quad_tree(y, x, n, arr):
        nonlocal answer
        if n == 1:
            answer[arr[y][x]] += 1
            return

        flag = arr[y][x]
        isPossible = True

        for i in range(y, y + n):
            for j in range(x, x + n):
                if flag == arr[i][j]:
                    continue
                else:
                    isPossible = False
                    break
            if not isPossible:
                break

        if isPossible:
            answer[flag] += 1
            return
        else:
            quad_tree(y, x, n // 2, arr)
            quad_tree(y+n//2, x, n//2, arr)
            quad_tree(y, x+n//2, n//2, arr)
            quad_tree(y+n//2, x+n//2, n//2, arr)

---

전체 코드

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

    def quad_tree(y, x, n, arr):
        nonlocal answer
        if n == 1:
            answer[arr[y][x]] += 1
            return

        flag = arr[y][x]
        isPossible = True

        for i in range(y, y + n):
            for j in range(x, x + n):
                if flag == arr[i][j]:
                    continue
                else:
                    isPossible = False
                    break
            if not isPossible:
                break

        if isPossible:
            answer[flag] += 1
            return
        else:
            quad_tree(y, x, n // 2, arr)
            quad_tree(y+n//2, x, n//2, arr)
            quad_tree(y, x+n//2, n//2, arr)
            quad_tree(y+n//2, x+n//2, n//2, arr)

    quad_tree(0, 0, N, arr)
    return answer