[분할정복] 2차원배열을 n조각 내는 문제유형

2차원 배열을 n조각 내는 문제유형은 다음과 같은 순서로 푼다.

1.
2차원 배열의 왼쪽 위를 기준으로,
x, y좌표와 2차원배열의 크기 n을 입력받아 모든 원소가 똑같은지 체크해주는 함수를 만든다.

2.
n조각 내는 재귀함수를 만든다.
- 모든 원소가 똑같을 경우 값을 리턴하는 종료조건을 만든다.
- 종료조건이 아닐 경우, n조각으로 자르기 위해 가중치 w를 설정한다. (w = N / n)
- 이중 반복문으로 n조각 개수만큼 재귀함수를 호출한다.
(ex : 4조각 -> (0..<2)(0..<2), 9조각 -> (0..<3)(0..<3))

 

예시코드

import Foundation

let N = Int(readLine()!)!

var board = [[Int]]()
var counts = [0, 0]

for _ in 0..<N {
    let numArr = readLine()!.components(separatedBy: " ").map { Int($0)! }
    board.append(numArr)
}

// 모든 원소가 똑같은지 체크
func check(x: Int, y: Int, n: Int) -> Bool {
    for i in x..<x+n {
        for j in y..<y+n {
            if board[x][y] != board[i][j] {
                return false
            }
        }
    }
    return true
}

// 색종이 자르는 함수
func cut(x: Int, y:Int, n: Int) {
    if check(x: x, y: y, n: n) {
        counts[board[x][y]] += 1
        return
    } else {
        let w = n / 2    // 잘린 조각을 위한 가중치
        // 4조각으로 나누기 때문에 (0..<2) (0..<2) 이중반복돌림
        for i in 0..<2 {
            for j in 0..<2{
                cut(x: x+i*w, y: y+j*w, n: w)
            }
        }
    }
}

cut(x: 0, y: 0, n: N)
print(counts[0])
print(counts[1])