[백준] 2630번: 색종이 만들기 - Kotlin[코틀린]

문제

 

2630번: 색종이 만들기

 

---

풀이

 

 분할정복이란 큰 문제를 작은 문제로 나누어 해결하는 재귀적인 알고리즘이다. 일반적으로 세 단계로 구성된다.

 

 - 분할(Divide): 주어진 문제를 더 작은 부분 문제들로 분할한다. 부분 문제들은 원래 문제와 동일한 형태를 가진다.
 - 정복(Conquer): 부분 문제들을 재귀적으로 해결하여 부분 해를 구한다.
 - 통합(Combine): 작은 부분 문제들의 해를 결합하여 원래 문제의 해를 구한다.

 

 문제는 분할정복을 활용하여 종이의 색깔 개수를 세는 문제이다. 주어진 종이를 네 부분으로 나누어 재귀적으로 탐색하고 같은 색상으로 이루어진 종이를 찾을 때마다 해당하는 색의 개수를 세어준다.

 

---

코드

 

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

    val size = br.readLine().toInt()
    val paper = Array(size){ br.readLine().split(' ').map { it.toInt() } }

    var blue = 0
    var white = 0

    fun checkPaper(size: Int, x: Int, y: Int): Boolean {
        val color = paper[x][y]
        for(i in x until x+size) {
            for(j in y until y+size) {
                if(paper[i][j] != color) return false
            }
        }

        return true
    }

    fun divide(size: Int, x: Int, y: Int) {
        if (size == 1 || checkPaper(size, x, y)) {
            if (paper[x][y] == 1) blue++
            else white++
        } else {
            divide(size/2, x, y)
            divide(size/2, x + size/2, y)
            divide(size/2, x, y + size/2)
            divide(size/2, x + size/2, y + size/2)
        }
    }

    divide(size, 0, 0)

    bw.write("$white\n$blue")
    bw.flush()
    bw.close()
    br.close()
}