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

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

프로그래머스

코드

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

풀이

• DFS로 해결할 수 있었다.
• 탐색할 때 기준 값이랑 다르면 더 쪼개야하므로 n의 절반씩 쪼개어 dfs를 실행하면 된다.