[BOJ] 14601 샤워실 바닥 깔기 (Large) - P5

TaeGN·2024년 9월 16일

algorithm kotlin

BOJ Platinum Challenge

목록 보기

83/114

문제풀이

2^k x 2^k의 정사각형을 4등분 하며 샤워실 바닥을 깔아준다.

주의사항

정사각형의 네 귀퉁이 중에 한 부분이 빠져있는 도형을 채우는 것을 반복한다.

소요시간

50분

package 백준.Platinum.P5.p14601_샤워실바닥깔기_Large

val dr = intArrayOf(0, 0, 1, 1)
val dc = intArrayOf(0, 1, 0, 1)
fun main() {
    val K = readln().toInt()
    val (r, c) = readln().split(" ").map(String::toInt).let { ((1 shl K) - it[1]) to (it[0] - 1) }
    val matrix = Array(1 shl K) { IntArray(1 shl K) }.apply { this[r][c] = -1 }
    var count = 1
    fun dfs(sr: Int, sc: Int, k: Int, tr: Int, tc: Int) {
        if (k == 1) {
            for (i in 0 until 2) {
                for (j in 0 until 2) {
                    if (sr + i != tr || sc + j != tc) matrix[sr + i][sc + j] = count
                }
            }
            count++
            return
        }
        val size = 1 shl k
        val nk = k - 1
        val nSize = 1 shl nk
        val targetD = when {
            tr in sr until (sr + nSize) && tc in sc until (sc + nSize) -> 0
            tr in sr until (sr + nSize) && tc in (sc + nSize) until (sc + size) -> 1
            tr in (sr + nSize) until (sr + size) && tc in sc until (sc + nSize) -> 2
            tr in (sr + nSize) until (sr + size) && tc in (sc + nSize) until (sc + size) -> 3
            else -> throw IllegalArgumentException()
        }
        for (d in dr.indices) {
            if (d != targetD) matrix[(sr + nSize - 1) + dr[d]][(sc + nSize - 1) + dc[d]] = count
        }
        count++
        for (d in dr.indices) {
            val nr = sr + nSize * dr[d]
            val nc = sc + nSize * dc[d]
            if (d == targetD) dfs(nr, nc, nk, tr, tc)
            else dfs(nr, nc, nk, (sr + nSize - 1) + dr[d], (sc + nSize - 1) + dc[d])
        }
    }
    dfs(0, 0, K, r, c)
    println(matrix.joinToString("\n") { it.joinToString(" ") })
}