Programmers / 쿼드압축 후 개수 세기 / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 쿼드압축 후 개수 세기 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/68936

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

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

    rows = len(arr)

    def qu(x, y, n):
        first = arr[x][y]
        for i in range(x, x + n):
            for j in range(y, y + n):
                if first != arr[i][j]:
                    nrows = n // 2
                    qu(x, y, nrows)
                    qu(x + nrows, y, nrows)
                    qu(x, y + nrows, nrows)
                    qu(x + nrows, y + nrows, nrows)
                    return 0
        answer[first] += 1

    qu(0, 0, rows)

    return answer

 

그림처럼 처음에 모두가 같은 숫자일 경우에서 점점 반으로 쪼개지면서 나가아가는 코드의 방식이다.

---

※ 알아야 할 것

 

if문 안에return 0을 붙이지 않으면 숫자가 다른 것을 인지했어도 계속 진행을 하면서 불필요한 쿼드압축의 수를 구하게 된다.