[백준/Swift] 2630 색종이

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 2630 색종이 만들기
• 제출 언어: Swift
• 알고리즘 분류:
  • 분할정복
  • 재귀

풀이

우선 2차원 배열을 생성하여 입력 값을 넣어준 후에,  다양한 경우의 수로 나누어서 처리를 해주었다 .

분할정복이므로 자를 색종이의 배열과, 현재  배열의 크기를 인자로 받는 재귀함수로 구현하였고,

종료조건을 해당 배열의 크기가 1일 때, 해당 색종이의 색에 따라 count에 1을 더해주고 해당 재귀를 종료하도록 하였다.

이 문제에서 중요한 것은 색종이 한 칸의 개수를 세는 것이 아니고 잘라진 색종이의 개수를 세므로 1씩만 더해주면 된다.

func cutConfetti(_ tempArr: [[Int]], _ size: Int) {
    // 더 이상 자를 색종이가 없는 경우
    if size == 1 {
        if tempArr[0][0] == 0 {
            whiteCount += 1
        } else {
            blueCount += 1
        }
        return
    }
    
    let tempArrFlat = tempArr.flatMap{$0}
    
    // 해당 색종이가 모두 한 가지색으로 구성되어 있는 경우
    if tempArrFlat.reduce(1){$0 * $1} == 1 {
        blueCount += 1
        return
    }
    if tempArrFlat.reduce(0){$0 + $1} == 0 {
        whiteCount += 1
        return
    }
    
    // 해당 색종이가 여러 색으로 구성되어 있는 경우
    cutConfetti(splitConfetti(tempArr, (0, size/2), (0, size/2)), size/2)
    cutConfetti(splitConfetti(tempArr, (0, size/2), (size/2, size)), size/2)
    cutConfetti(splitConfetti(tempArr, (size/2, size), (0, size/2)), size/2)
    cutConfetti(splitConfetti(tempArr, (size/2, size), (size/2, size)), size/2)
}

나는 위의 함수와 같이 경우의 수를 나누었다. 

1. 더 이상 자를 색종이가 없는 경우
(종료 조건, size == 1)

2. 해당 색종이가 모두 한 가지색으로 구성되어 있는 경우
( 해당 색의 count += 1을 해주고 종료해주면 된다 )

• 파란색 색종이가 1로 구성되어 있으므로 모든 배열의 값을 곱해서 1이면 모든 색종이가 파란색임
• 하얀색 색종이가 0으로 구성되어 있으므로 모든 배열의 값을 더해서 0이면 모든 색종이가 하얀색임

3. 해당 색종이가 여러 색으로 구성되어 있는 경우
( 색종이를 4등분해서 잘라야한다 )

 

// 색종이를 4등분하는 함수, 자를 색종이 배열과 해당 넓이와 높이의 좌표값을 인자로 받아 자른 색종이 배열을 반환한다
func splitConfetti(_ tempArr: [[Int]], _ width: (Int, Int), _ height: (Int, Int)) -> [[Int]] {
    var arr: [[Int]] = []
    for idx in height.0..<height.1 {
        arr.append(Array(tempArr[idx][width.0..<width.1]))
    }
    return arr
}

 

전체 코드

import Foundation

let N = Int(readLine()!)!
var arr: [[Int]] = Array(repeating: [], count: N)
for i in 0..<N {
    arr[i] = Array(readLine()!.split(separator: " ").map{Int(String($0))!})
}
var whiteCount = 0
var blueCount = 0
func cutConfetti(_ tempArr: [[Int]], _ size: Int) {
    if size == 1 {
        if tempArr[0][0] == 0 {
            whiteCount += 1
        } else {
            blueCount += 1
        }
        return
    }
    
    let tempArrFlat = tempArr.flatMap{$0}
    
    if tempArrFlat.reduce(1){$0 * $1} == 1 {
        blueCount += 1
        return
    }
    if tempArrFlat.reduce(0){$0 + $1} == 0 {
        whiteCount += 1
        return
    }
    cutConfetti(splitConfetti(tempArr, (0, size/2), (0, size/2)), size/2)
    cutConfetti(splitConfetti(tempArr, (0, size/2), (size/2, size)), size/2)
    cutConfetti(splitConfetti(tempArr, (size/2, size), (0, size/2)), size/2)
    cutConfetti(splitConfetti(tempArr, (size/2, size), (size/2, size)), size/2)
}

func splitConfetti(_ tempArr: [[Int]], _ width: (Int, Int), _ height: (Int, Int)) -> [[Int]] {
    var arr: [[Int]] = []
    for idx in height.0..<height.1 {
        arr.append(Array(tempArr[idx][width.0..<width.1]))
    }
    return arr
}
cutConfetti(arr, N)

print(whiteCount)
print(blueCount)