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

https://school.programmers.co.kr/learn/courses/30/lessons/68936?language=python3 

프로그래머스

 

 

1. 해결방법

생각보다 해결할 수 있는 아이디어가 금방 떠올랐다.

예제1로 생각을 하면 처음에는 큰 사각형을 탐색을 시작하고, 그 다음에는 4등분으로 쪼개져서 탐색을 한다.
이때, (0, 0), (0, 2), (2, 0), (2, 2)가 시작점이 된다. 시작점의 값은 0 또는 1이므로 사각형을 탐색했을 때, 시작점의 값과 다르다면 dfs 백트래킹을 이용해서 다시 한번 사각형을 나누는 작업이 필요하다.

백트래킹에서는 사각형을 나누는 범위도 너무 중요했다. 4개로 쪼개지기 때문에 당연히 4개의 재귀함수가 호출된다는 것도 이해해야 한다. length는 당연히 // 2로 두어야 길이가 일정한 정사각형이 만들어진다.

만약 나누지 않고 for문을 다 돌렸다면 한 사각형 내의 값이 동일하다는 것이므로 합쳐야 한다. 굳이 물리적으로 합치지 않아도 for문을 다 돌았다는 의미는 곧 같은 값을 가진 의미이기에 answer에 +1만 해주면 된다. 

 

 

2. 정답코드

def solution(arr):
    answer = [0, 0]
    
    def dfs(y, x, lens):
        start = arr[y][x]
        
        for i in range(y, y + lens):
            for j in range(x, x + lens):
                if start != arr[i][j]:
                    lens = lens // 2
                    dfs(y, x, lens)
                    dfs(y, x + lens, lens)
                    dfs(y + lens, x, lens)
                    dfs(y + lens, x + lens, lens)
                    return
    
        answer[start] += 1
        
    # main
    lens = len(arr)
    dfs(0, 0, lens)
    
    return answer