[월간 코드 챌린지 1 / 프로그래머스] 68936번 : 쿼드압축 후 개수

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

 

Lv2 문제다!

크기가 절반씩 줄어들면서 같은 로직을 반복해서 재귀함수로 풀어야겠다는 건 알았는데, 이게 바로 손이 가지 않았다. 

시작점의 위치를 기준으로 n 크기 만큼의 정사각형들을 탐색하면된다 

 

풀이 로직

• 리스트를 실제 자르지 말고 나뉘는 인덱스만 구해서 해결하는 것이 좋다.
• 인덱스를 구할 때는 네모의 시작점의 위치만 구한다. 거기에서 네모의 길이만큼 더해주면 네모를 완성시킨다.
• 재귀함수는 시작 지점의 위치와 각 네모의 길이를 매개변수로 넘기면 된다.
• 네모 내부에서 시작점의 값과 다른 값이 있다면 바로 작은 단위로 넘어간다
• 압축에 성공했다면 네모의 시작값의 위치에 + 1 해준다

 

- 정답 풀이 :

return을 안 하면 함수가 제때 종료가 되지 않아 틀린 답을 출력한다

이 과정이 이해가 가지 않아 python tutor를 돌렸더니,

comp 과정 중에 answer[init] += 1까지 간 함수들이 None을 반환하고,(?)

각각의 comp가 실행되다가 마지막 comp가 나오면 return을 통해 해당 깊이의 재귀를 빠져나온다 (?) 

def solution(arr):
    answer = [0, 0]
    N = len(arr)
    
    def comp(x, y, n):
        init = arr[x][y]
        for i in range(x, x + n):
            for j in range(y, y + n):
                if arr[i][j] != init:
                    m = n // 2
                    comp(x, y, m)
                    comp(x, y + m, m)
                    comp(x + m, y, m)
                    comp(x + m, y + m, m)
                    return
                
        #무사히 다 통과했다면 압축가능         
        answer[init] += 1
        
    comp(0, 0, N)
    
    return answer