[Swift] 백준 2630번 색종이 만들기

링크: https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 

 

이 문제의 풀이는 핵심 풀이는 '모두 같은 색상이 아니라면 1/4씩 쪼개 4번을 더 탐색한다.' 입니다.

 

1. 전부 같은 색상인 경우

array의 색상의 갯수를 +1합니다.

 

2. 전부 같은 색상이 아닌 경우

1/4씩 쪼개 4번의 탐색을 진행합니다.

 

isSameColor 함수의 경우 reduce로도 계산이 가능하지만 성능 향상을 기대하기 위해 for문으로 작성하였습니다.

import Foundation

let N = Int(readLine()!)!

var array = [[Int]]()
var zero = 0
var one = 0

for _ in 0..<N {
    let arr = readLine()!.split(separator: " ").map { Int($0)! }
    array.append(arr)
}

func isSameColor(_ array: [[Int]]) -> Bool {
    let first = array.first!.first
    
    for i in array {
        for j in i {
            if j != first { return false }
        }
    }
    
    return true
}

func addZeroOrOne(_ array: [[Int]]) {
    if !array.isEmpty {
        if array.first!.first == 0 {
            zero += 1
        } else {
            one += 1
        }
    }
}

func divide(_ array: [[Int]]) {
    if array.count == 1 { // 1. 전부 같은 색상인 경우
        addZeroOrOne(array)
    } else {
        if !isSameColor(array) { // 2. 전부 같은 색상이 아닌 경우
            let half = array.count / 2
            
            // 4분의 1로 나누기
            divide(array[0..<half].map { $0[0..<half].compactMap { $0 }})
            divide(array[0..<half].map { $0[half..<array.count].compactMap { $0 }})
            divide(array[half..<array.count].map { $0[0..<half].compactMap { $0 }})
            divide(array[half..<array.count].map { $0[half..<array.count].compactMap { $0 }})
        } else { // 1. 전부 같은 색상인 경우
            addZeroOrOne(array)
        }
    }
}

divide(array)

print(zero)
print(one)