[BOJ] 14939 불 끄기 - P4

TaeGN·2024년 8월 4일

algorithm kotlin

BOJ Platinum Challenge

목록 보기

3/114

문제풀이

(0, 0) ~ (8, 8)를 순회하며 불이 켜져있으면 바로 밑에 칸의 스위치를 누른다.
마지막 줄 (9, 0) ~ (9, 9)에서 불이 켜져있으면 불가능한 경우이다.
첫번째 줄의 스위치를 누를 경우도 고려해야 하므로 부분 집합을 활용한다.
최소값을 출력한다.

주의사항

원활한 스위치 조작을 위해 BulbMatrix class를 생성하였다.

소요시간

45분

package 백준.Platinum.P4.p14939_불끄기

import kotlin.math.min

class BulbMatrix(private val flags: IntArray = IntArray(SIZE)) {
    companion object {
        const val SIZE = 10
        const val IMPOSSIBLE = Int.MAX_VALUE shr 4
        val dr = listOf(0, 1, 0, -1)
        val dc = listOf(1, 0, -1, -1)
    }

    fun set(r: Int, c: Int, isOn: Boolean) {
        if (isOn) flags[r] = flags[r] or (1 shl c)
    }

    fun minCount(): Int {
        fun sequence(r: Int = 0, c: Int = 0): Int {
            if (r == SIZE) return 0
            if (isOn(r, c)) {
                if (r == SIZE - 1) return IMPOSSIBLE
                switch(r + 1, c)
                val count = sequence(r + (c + 1) / SIZE, (c + 1) % SIZE)
                switch(r + 1, c)
                return 1 + count
            }
            return sequence(r + (c + 1) / SIZE, (c + 1) % SIZE)
        }

        fun minCount(idx: Int = 0, count: Int = 0): Int {
            if (idx == SIZE) return count + sequence()
            var minCount = minCount(idx + 1, count)
            switch(0, idx)
            minCount = min(minCount, minCount(idx + 1, count + 1))
            switch(0, idx)
            return minCount
        }

        val minCount = minCount()
        return if (minCount >= IMPOSSIBLE) -1 else minCount
    }

    private fun isOn(r: Int, c: Int) = flags[r] and (1 shl c) != 0
    private fun switch(r: Int, c: Int) {
        flags[r] = flags[r] xor (1 shl c)
        for (d in dr.indices) {
            val nr = r + dr[d]
            val nc = c + dc[d]
            if (nr in 0 until SIZE && nc in 0 until SIZE) {
                flags[nr] = flags[nr] xor (1 shl nc)
            }
        }
    }
}

fun main() = with(System.`in`.bufferedReader()) {
    val bulbMatrix = BulbMatrix()
    repeat(BulbMatrix.SIZE) { r ->
        val input = readLine()
        repeat(BulbMatrix.SIZE) { c ->
            bulbMatrix.set(r, c, input[c] == 'O')
        }
    }
    println(bulbMatrix.minCount())
}