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

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

프로그래머스

 

접근

---

• 전부 0 또는 1을 만족하지 않는 경우, 길이를 반으로 줄여서 탐색해 나가야 한다 → DFS 

 

로직

---

• 0과 1의 개수를 담을 answer를 배열로 선언하고 각각 0으로 초기화한다
• dfs 메서드는 행, 열, 길이 정보를 매개변수로 가진다
• 현재 탐색하는 구간에서 모두 1일 경우, 1의 개수를 하나 증가시킨다
• 현재 탐색하는 구간에서 모두 0일 경우, 0의 개수를 하나 증가시킨다
• 모두 동일한 값이 아닐 경우, 길이를 반으로 줄인 범위에서 탐색을 진행한다

 

코드

---

1. Python 풀이

---

def solution(arr):
    
    answer = [0,0]
    
    def allSatisfy(row, col, length, value):
        for i in range(row, row+length):
            for j in range(col, col+length):
                if arr[i][j] != value:
                    return False
        return True
    
    def dfs(row, col, length):
        
        if allSatisfy(row, col, length, 1):
            answer[1] += 1
        elif allSatisfy(row, col, length, 0):
            answer[0] += 1
        else :
            newLen = int(length/2)
            for (i, j) in [(row, col),(row+newLen, col),(row, col+newLen),(row+newLen, col+newLen)]:
                dfs(i, j, newLen)
            
    dfs(0,0,len(arr))
    
    return answer

 

2. Swift 풀이

---

import Foundation

func solution(_ arr:[[Int]]) -> [Int] {
    
    var answer = [0,0]
    
    func allSatisfy(_ row: Int, _ col: Int, _ length: Int, _ value: Int) -> Bool {
        for i in row..<row+length {
            for j in col..<col+length {
                if arr[i][j] != value {
                    return false
                }
            }
        }
        return true
    }
    
    func dfs(_ row: Int, _ col: Int, _ length: Int) {
        if allSatisfy(row,col,length,1) {
            answer[1] += 1
        }
        else if allSatisfy(row, col, length, 0) {
            answer[0] += 1
        }
        else {
            for (i, j) in [(row, col), (row+length/2, col), (row, col+length/2), (row+length/2, col+length/2)] {
                dfs(i, j, length/2)
            }
        }
    }
    
    dfs(0,0,arr.count)
    
    return answer
}