프로그래머스 [Lv. 2] 쿼드압축 후 개수 세기 {언어 : Python}

문제 링크

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

프로그래머스

정답 코드

answer = [0, 0]
def solution(arr):
    n = len(arr)
    def dfs(n, r, c):
        global answer
        
        currentV = arr[r][c]
        isValid = True
        for nr in range(r, n+r):
            for nc in range(c, n+c):
                nextV = arr[nr][nc]
                if currentV != nextV:
                    isValid = False
                    break
            if isValid == False:
                break
        if isValid:
            answer[currentV] += 1
        else:
            half = n // 2
            dfs(half, r, c)
            dfs(half, r+half, c)
            dfs(half, r, c+half)
            dfs(half, r+half, c+half)
            
    dfs(n, 0, 0)
    return answer

풀이 방법

1. 범위와 시작지점 r과 c를 파라미터로 하는 dfs 함수를 만든다.
2. 현재 n 과 r, c로 만든 범위에서 값들이 모두 같은지 확인한다.
3. 값들이 1 또는 0으로 통일되었다면 isValid는 True가 되고 answer에 해당 숫자에 1을 더해준다.
4. 아닌 경우 이제 4등분을 해야하므로 dfs를 4 부분으로 나눈다.
   1. n을 2로 나눠서 half를 만든다.
   2. 쉽게 말해 n이 4인 경우
      1. dfs(2, 0, 0)
      2. dfs(2, 2, 0)
      3. dfs(2, 0, 2)
      4. dfs(2, 2, 2)
5. answer를 반환한다.

느낀점

• 전에는 어떻게 풀어야 할지 감도 못잡았는데 이제는 꽤 쉽게 푸는 나를 보며 뿌듯함을 느꼈다.