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

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

 

📚 코드

// 다른 분 풀이 참조
def solution(arr):
    N = len(arr)
    answer = [0, 0]

    def compress(x, y, N):
        init = arr[x][y]
        for r in range(x, x + N):
            for c in range(y, y + N):
                if arr[r][c] != init:
                    N //= 2
                    compress(x, y, N)
                    compress(x, y + N, N)
                    compress(x + N, y, N)
                    compress(x + N, y + N, N)
                    return

        answer[init] += 1
    compress(0, 0, N)
    
    return answer

 

🌁  접근 방법

1. 전체 사각형을 우선 기준으로 ,

2. 모든 요소를 순회하면서 서로 동일한지 체크한다.

3. 동일하지 않다면 분기하여, 전체 사각형을 사등분으로 쪼갠 후 네 개의 서로 다른 사각형에 작두 타듯 재귀함수를 태운다.

그림 상에선 하나의 사각형으로만 재귀를 타는 것 같지만, 비어있는 나머지 세 부분으로도 각자 재귀를 태우면 된다.

재귀는 사각형 내부의 모든 값이 동일할 때 멈추고, 가장 작은 사각형에 도달하면 필연적으로 if 조건문이 True 이므로 재귀를 벗어나게 된다.

 

 

🕹  실수한 코드

리턴을 잘못된 위치에서 선언해서 에러가 발생했는데, 

compress() 함수가 어디서 return 돼야 하는지 파악해야한다.

return 은 if 문 내부에 있어야하는데, 탐색하고자 하는 사각형에서 하나라도 다른 요소가 있다면 재귀를 타는 조건문이다. 

정사각형 내부 값이 모두 같지 않으므로 새로운 사각형을 기준으로 재귀를 태운 후 리턴하여 해당 함수를 종료 시켜야 한다.

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

    def compress(x, y, N):
        init = arr[x][y]
        for r in range(x, x + N):
            for c in range(y, y + N):
                if arr[r][c] != init:
                    N //= 2
                    compress(x, y, N)
                    compress(x, y + N, N)
                    compress(x + N, y, N)
                    compress(x + N, y + N, N)


        answer[init] += 1
        return   # 리턴이 여기있으면 오답이다.
    compress(0, 0, N)
    
    return answer