[프로그래머스]쿼드 압축 후 개수 세기

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

프로그래머스

풀이

쿼드 압축 문제는 전형적인 분할 정복 문제인 것 같다. 비슷한 유형의 문제를 풀어본 적이 있어 분할정복을 바로 떠올렸다. 쿼드 압축에서 n의 값은 2의 배수이기 때문에 2의 단위로 끊어가며 정복해가면 되겠다. 일단 quadzip이라는 함수를 만들고, 이중 for문으로 처음에 시작한 이진수(1, 0)이랑 다른 값이 나오면 입력으로 받은 시작 행, 끝나는 행, 시작 열, 끝나는 열 값을 4개로 나눈다음 각각 재귀로 다시 한번 quadzip함수를 호출하면 된다. 만약 모든 요소가 다 같은 값일 경우 압축이 된 것이므로 맨 처음에 이진수에 따라 answer의 인덱스에 더해주면 되겠다.

def quadzip(r1, r2, c1, c2):
    global image
    global answer
    binary = image[r1][c1]
    flag = False
    for i in range(r1, r2):
        for j in range(c1, c2):
            if image[i][j] != binary:
                flag = True
                quadzip(r1, (r1+r2)//2, c1, (c1+c2)//2)
                quadzip(r1, (r1+r2)//2, (c1+c2)//2, c2)
                quadzip((r1+r2)//2, r2, c1, (c1+c2)//2)
                quadzip((r1+r2)//2, r2, (c1+c2)//2, c2)
                break
        if flag:
            break
    if not flag:
        answer[binary] += 1
def solution(arr):
    global answer
    answer = [0, 0]
    global image
    image = arr
    quadzip(0, len(arr), 0, len(arr[0]))
    return answer