[백준] 2630 (색종이 만들기)

#1 알고리즘

색종이를 정직하게 가로 절반 세로 절반씩 자르기 때문에 어렵지 않은 문제다. 이 정직한 조건이 없었더라면 훨씬 까다로웠을 것이다. 아래의 재귀 함수를 이용해 문제를 풀었다.

 

1. 색종이가 단색인 지 확인하고, 맞다면 해당 색의 갯수를 +1 하고 함수를 종료한다.
2-1. 현재 색종이를 가로 절반 세로 절반 자른 좌측 상단(↖) 색종이 범위에 대해 재귀 호출을 수행한다.
2-2. 현재 색종이를 가로 절반 세로 절반 자른 좌측 하단(↙) 색종이 범위에 대해 재귀 호출을 수행한다.
2-3. 현재 색종이를 가로 절반 세로 절반 자른 우측 상단(↗) 색종이 범위에 대해 재귀 호출을 수행한다.
2-4. 현재 색종이를 가로 절반 세로 절반 자른 우측 하단(↘) 색종이 범위에 대해 재귀 호출을 수행한다.

 

#2 코드 - 코틀린

lateinit var paperMap: Array<Array<Int>>
var sideLength = 0
var whiteCount = 0
var blueCount = 0

fun main() {
    sideLength = readln().toInt()
    paperMap = Array(sideLength) { Array(sideLength) { 0 } }

    for (i in 0..<sideLength) {
        val row = readln().split(" ")

        for (j in 0..<sideLength) {
            if (row[j].toInt() == 1) {
                paperMap[i][j] = 1
            }
        }
    }

    findColorPaper(0..<sideLength, 0..<sideLength)

    println(whiteCount)
    println(blueCount)
}

fun findColorPaper(rangeY: IntRange, rangeX: IntRange) {
    if (isHaveOnlyOneColor(rangeY, rangeX)) {
        if (paperMap[rangeY.first][rangeX.first] == 0) {
            whiteCount++
        } else {
            blueCount++
        }

        return
    }

    // ↖
    findColorPaper(frontHalf(rangeY), frontHalf(rangeX))

    // ↙
    findColorPaper(frontHalf(rangeY), rearHalf(rangeX))

    // ↗
    findColorPaper(rearHalf(rangeY), frontHalf(rangeX))

    // ↘
    findColorPaper(rearHalf(rangeY), rearHalf(rangeX))
}

fun isHaveOnlyOneColor(rangeY: IntRange, rangeX: IntRange): Boolean {
    val firstElement = paperMap[rangeY.first][rangeX.first]

    for (y in rangeY) {
        for (x in rangeX) {
            if (paperMap[y][x] != firstElement) {
                return false
            }
        }
    }

    return true
}

// 반으로 나뉜 범위의 앞 부분
fun frontHalf(range: IntRange): IntRange {
    if (range.count() <= 2) {
        return range.first..range.first

    } else {
        return range.first..<range.first + (range.count() / 2)
    }
}

// 반으로 나뉜 범위의 뒷 부분
fun rearHalf(range: IntRange): IntRange {
    if (range.count() <= 2) {
        return range.last..range.last

    } else {
        return range.first + (range.count() / 2)..range.last
    }
}