백준 2630번 색종이 만들기 - 스위프트(Swift) 풀이 + 그림 설명

 그림부터 너무 분할 정복처럼 생긴 분할 정복 문제.

1. 색종이를 4개로 쪼갠다.
2. 재귀적으로 4개의 조각에 대해 각각 하얀색과 파란색의 개수를 센다.
3. 4개 조각에서 구한 하얀색과 파란색의 개수를 더해 전체 개수를 구한다.
4. 만약 4개 조각이 모두 같은 색인 경우, 같은 색이 4개 있는 것이 아니라 큰 하나의 색종이인 것을 조심한다.

---

1. 색종이를 4개로 쪼갠다.

 모두 같은 색이면 더 이상 자르지 말라고 했다. 하지만 생각을 달리해서 일단 자른 다음에, 모두 같은색이면 다시 붙일 것이다..!

 

2. 재귀적으로 4개의 조각에 대해 각각  하얀색과 파란색의 개수를 센다.

 다음과 같은 함수를 정의했다. 전체 종이에서 (row, col)이 왼쪽 꼭짓점이고, 크기가 size인 조각 내의 (하얀색 수, 파란색 수)를 리턴하는 countColor 함수이다. 최종적으로 알아야 하는 것은 countColor(row: 0, col: 0, size: N)이 된다.

func countColor(row: Int, col: Int, size: Int) -> (Int, Int)

 

 4개 조각에 대해 하얀색과 파란색 색종이 몇 개씩으로 이루어졌는지 각각 세준다. 각 조각의 꼭짓점은 아래와 같이 (row, col), (row, col + size/2), (row + size/2, col), (row + size/2, col + size/2)가 된다. 이 4칸에 대해 countColor를 호출한다.

 

 재귀의 종료 조건은 size = 1일 때가 된다. size = 1이면 더 이상 쪼갤 수 없기 때문에.

 

3. 4개 조각에서 구한 하얀색과 파란색의 개수를 더해 전체 개수를 구한다.

 4개 조각에 대해 countColor를 호출해서 얻은 4개의 더해서 하얀색 종이 개수, 파란색 종이 개수의 총합을 구한다. 

 

4. 만약 4개 조각이 모두 같은 색인 경우, 같은 색이 4개 있는 것이 아니라 큰 하나의 색종이인 것을 조심한다.

 만약 어느 한 색깔이 0개이면, 모두 같은 색이므로 다시 쪼갰던 종이를 다시 붙여주자. 예를 들어 하얀색만 4개가 나왔다고 하면, (4, 0)이 아니라 다시 4개 조각을 하나로 붙여서 (1, 0)을 리턴해주어야 한다.

 

---

import Foundation

var paper = Array(repeating: Array(repeating: 0, count: 128), count: 128)

typealias Color = (white: Int, blue: Int)

func countColor(row: Int, col: Int, size: Int) -> Color {
    // Base Case
    if size == 1 {
        if paper[row][col] == 1 { return (0, 1) }
        else { return (1, 0) }
    }
    
    var white = 0
    var blue = 0
    
    let rowPoint = [row, row + size / 2]
    let colPoint = [col, col + size / 2]
    
    for i in 0..<2 {                    // 4분면으로 나눠서 각각 카운트 후 합침
        for j in 0..<2 {
            let quadrant = countColor(row: rowPoint[i],
                                      col: colPoint[j],
                                      size: size / 2)
            white += quadrant.white
            blue += quadrant.blue
        }
    }
    
    if white == 0 { return (0, 1) }     // 4분면의 색이 모두 같으면 자르지 않음
    if blue == 0 { return (1, 0) }
    
    return (white, blue)
}

let N = Int(readLine()!)!
for i in 0..<N {
    let row = readLine()!.split(separator: " ").map{ Int(String($0))! }
    row.enumerated().forEach{ paper[i][$0] = $1 }
}

let result = countColor(row: 0, col: 0, size: N)

print(result.white)
print(result.blue)