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

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

 

접근 방식

 

큰 정사각형을 네 사분면으로 쪼개 내려가는 분할 정복 문제.

 

n x n 영역이 모두 같은 값이면 그 값(0 또는 1)의 개수를 하나 올리고 멈춤. 한 칸이라도 값이 다르면 n/2 크기의 네 사분면으로 나눠 각각 재귀함. 더 쪼갤 수 없는 n = 1까지 내려가면 그 칸을 그대로 셈.

 

예전 학교 수업에서는 작은 문제를 합쳐 큰 문제로 올라가는 분할 정복을 다뤘는데, 이번에는 큰 영역에서 작은 영역으로 내려가는 방향이었음.

 

코드

 

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

struct p68936 {
    static func run() {
        print(p68936.solution([[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]])) // [4,9]
    }
    
    static var zeroCount = 0
    static var oneCount = 0
    
    static func solution(_ arr:[[Int]]) -> [Int] {
        // 재귀 쓰면 금방 풀겠다! -> divide and conquer 해야한다.
        
        reculsive(arr: arr, row: 0, col: 0, n: arr.count)
        return [zeroCount, oneCount]
    }
    
    static func reculsive(arr: [[Int]], row: Int, col: Int, n: Int) {
        let point = arr[row][col] // 시작하는 지점
        
        for i in row..<row + n {
            for j in col..<col + n {
                if point != arr[i][j] {
                    reculsive(arr: arr, row: row, col: col, n: n/2)
                    reculsive(arr: arr, row: row, col: col + n/2, n: n/2)
                    reculsive(arr: arr, row: row + n/2, col: col, n: n/2)
                    reculsive(arr: arr, row: row + n/2, col: col + n/2, n: n/2)
                    
                    return
                }
            }
        }
        
        // 하나의 영역으로 묶였을 경우 or 끝까지 묶이지 않아 n이 1인 경우
        if point == 1 { oneCount += 1 }
        else { zeroCount += 1}
    }
}