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

0.  문제 링크

 

 

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

프로그래머스

---

1.  풀이 방법

 

 

1. Divide and Conquer 방식을 사용했고, 트리 내에서는 반복문을 사용하여 문제를 해결하였다.
2. 첫 번째 숫자인 bef와 반복문에서 나오는 숫자가 다를 경우 압축이 불가능하므로, 해당 트리를 사등분하여 재귀를 호출했다.
3. 사등분 한 쿼드 트리를 모두 호출한 이후에는 return을 함으로써, 반복문을 바로 종료했다. -> 트리를 사등분하면 더 이상 볼 필요가 없음.

---

2.  코드

 

 

def solution(arr):
    def encode(y, x, l):
        # l == 1이면 어차피 아래 반복문에서 처리됨
        bef = arr[y][x]     # 최초 번호, 다른 수는 최초 번호와 무조건 같아야함.
        for i in range(y, y + l):
            for j in range(x, x + l):
                if arr[i][j] != bef:        # 다르면 쿼드트리
                    encode(y, x, l // 2)
                    encode(y, x + l // 2, l // 2)
                    encode(y + l // 2, x, l // 2)
                    encode(y + l // 2, x + l // 2, l // 2)
                    return
        else:
            answer[bef] += 1
        
        
    answer = [0, 0]
    encode(0, 0, len(arr))
    
    return answer

---

3.  마무리