[백준] 1992번: 쿼드트리 - Kotlin[코틀린]

문제

 

1992번: 쿼드트리

 

---

풀이

 

 분할정복을 활용해 풀이하면된다. 데이터를 네 부분으로 나누어 재귀적으로 탐색하는데, 탐색할 때마다 괄호를 열고 닫아주면 된다. 같은 데이터로 이루어진 부분을 찾으면 해당 숫자를 출력해준다.

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val size = br.readLine().toInt()
    val arr = Array(size) { br.readLine().map { it - '0' }.toIntArray() }

    fun checkData(size: Int, x: Int, y: Int): Boolean {
        val first = arr[x][y]

        for (i in x until x + size) {
            for (j in y until y + size) {
                if (arr[i][j] != first) return false
            }
        }

        return true
    }

    fun divide(size: Int, x: Int, y: Int) {
        if (size == 1 || checkData(size, x, y)) {
            bw.append(if (arr[x][y] == 1) "1" else "0")
        } else {
            bw.append("(")
            divide(size / 2, x, y)
            divide(size / 2, x, y + size / 2)
            divide(size / 2, x + size / 2, y)
            divide(size / 2, x + size / 2, y + size / 2)
            bw.append(")")
        }
    }

    divide(size, 0, 0)

    bw.write("")
    bw.flush()
    bw.close()
    br.close()
}