[Kotlin] 백준 2630 : 색종이 만들기

문제 링크

2630번: 색종이 만들기

---

---

문제 해설

기본적인 분할정복 문제다. 주어진 크기에 맞는 2차원 배열을 만든 후 전체 크기부터 검사를 시작해서 색종이로 사용할 수 없으면 4등분하여 다시 검사를 한다. 검사하는 중에 색종이로 사용할 수 있는 경우(=해당 구간의 모든 요소가 같은 경우)면 해당 색상의 색종이 개수를 1 증가시키고 해당 부분은 검사를 종료한다. 

---

Code

import java.util.StringTokenizer

val n = readln().toInt()
val paper = Array(n) { ByteArray(n) }
var w = 0
var b = 0

fun main() = with(System.`in`.bufferedReader()) {
    var st: StringTokenizer
    repeat(n) {
        st = StringTokenizer(readLine())
        paper[it] = ByteArray(n){ st.nextToken().toByte() }
    }
    cp(0, 0, n)
    println("$w\n$b")
}

fun cp(x: Int, y: Int, size: Int) {
    val next = size / 2
    var cnt = 0
    for (i in x until x + size) {
        for (j in y until y + size) {
            cnt += if (paper[i][j] == 1.toByte()) 1 else 0
        }
    }
    when (cnt) {
        size * size -> {
            b++
            return
        }
        0 -> {
            w++
            return
        }
    }
    cp(x, y, next)	// 왼쪽 위
    cp(x + next, y, next)	// 오른쪽 위
    cp(x, y + next, next)	// 왼쪽 아래
    cp(x + next, y + next, next)	// 오른쪽 아래
}