[백준/코틀린] 14500번: 테트로미노

링크

14500번: 테트로미노

풀이

테트로미노를 회전하거나 대칭했을 때 나올 수 있는 모든 모양을 고려하는 브루트포스 방식으로 해결합니다.

총 19가지 테트로미노 모양을 상대 좌표로 정의해 두고,
격자의 모든 위치에 올려 보며 네 칸의 합이 최대가 되는 경우를 찾습니다.

격자를 벗어나는 좌표를 처리하기 위해 종이의 바깥 영역을 유효하지 않은 값으로 채워 두고,
테트로미노의 네 칸이 모두 유효한 경우에만 합을 계산합니다.

코드

val dy = listOf(
    listOf(0, 0, 0, 0),
    listOf(0, 1, 2, 3),
    listOf(0, 0, 1, 1),
    listOf(0, 1, 2, 2),
    listOf(0, 0, 0, 1),
    listOf(0, 0, 1, 2),
    listOf(0, 1, 1, 1),
    listOf(0, 0, 1, 1),
    listOf(0, 1, 1, 2),
    listOf(0, 0, 0, 1),
    listOf(0, 1, 1, 2),
    listOf(0, 1, 1, 1),
    listOf(0, 1, 1, 2),
    listOf(0, 0, 1, 2),
    listOf(0, 1, 1, 1),
    listOf(0, 1, 2, 2),
    listOf(0, 0, 0, 1),
    listOf(0, 1, 1, 2),
    listOf(0, 0, 1, 1),
)
val dx = listOf(
    listOf(0, 1, 2, 3),
    listOf(0, 0, 0, 0),
    listOf(0, 1, 0, 1),
    listOf(0, 0, 0, 1),
    listOf(0, 1, 2, 0),
    listOf(0, 1, 1, 1),
    listOf(2, 0, 1, 2),
    listOf(1, 2, 0, 1),
    listOf(0, 0, 1, 1),
    listOf(0, 1, 2, 1),
    listOf(1, 0, 1, 1),
    listOf(1, 0, 1, 2),
    listOf(0, 0, 1, 0),
    listOf(0, 1, 0, 0),
    listOf(0, 0, 1, 2),
    listOf(1, 1, 0, 1),
    listOf(0, 1, 2, 2),
    listOf(1, 0, 1, 0),
    listOf(0, 1, 1, 2),
)

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    val paper = List(n + 3) { MutableList(m + 3) { -1 } }
    var ans = 0

    for (i in 0 until n) {
        val row = readln().split(" ").map { it.toInt() }

        for (j in 0 until m) {
            paper[i][j] = row[j]
        }
    }

    for (i in 0 until n) {
        for (j in 0 until m) {
            for (k in 0 until 19) {
                val tetromino = List(4) { paper[i + dy[k][it]][j + dx[k][it]] }

                if (tetromino.all { it != -1 }) ans = maxOf(ans, tetromino.sum())
            }
        }
    }

    println(ans)
}