백준 - 2630 색종이 만들기 (코틀린)

[문제]

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

2630번: 색종이 만들기

[코드]

private var n = 0
private lateinit var arr : Array<IntArray>
private var blueCnt = 0
private var whiteCnt = 0
fun main() {
    val br = System.`in`.bufferedReader()
    n = br.readLine().toInt()
    arr = Array(n){ IntArray(n){ 0 } }
    repeat(n){
        arr[it] = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    }
    slice(0,0,n)
    println(whiteCnt)
    println(blueCnt)
}
private fun slice(x:Int, y:Int,d:Int){
    if(d == 1 || !canSlice(x,y,d)){ // 길이가 1이거나 자를 수 있지 않을 때
        countColor(arr[x][y])
    }
    else {
        slice(x=x, y=y, d=d/2)
        slice(x=x+(d/2), y=y, d=d/2)
        slice(x=x, y=y+(d/2), d=d/2)
        slice(x=x+d/2, y=y+d/2, d=d/2)
    }
}
private fun canSlice(x:Int, y:Int,d:Int) : Boolean{
    for(i in x until x+d){
        for(j in y until y+d){
            if(arr[x][y] != arr[i][j])
                return true
        }
    }
    return false
}
private fun countColor(color:Int){
    if(color == 1)
        blueCnt += 1
    else
        whiteCnt += 1
}

[풀이]

재귀를 이용해서 풀었다.

slice라는 재귀함수를 통해 길이가 1이거나 자를 수 있지 않을 때는

색깔 수를 count하여 해당하는 색깔의 수를 1씩 늘려주고

그러한 제한 조건이 아닐 때는

길게 세로로 한번, 가로로 한번 잘라서 총 4개의 면이 나오도록 하기 위해

slice 재귀함수를 4번 쓴다.

이때 x,y좌표와 변의 길이 d를 이용하여 

해당하는 면을 구할수 있게끔 적절하게 변형하여 재귀를 돌린다.