[백준/코틀린] 17070번: 파이프 옮기기 1

링크

17070번: 파이프 옮기기 1

풀이

dp[y][x][d]: 끝이 (y, x)에 있고 방향이 d인 파이프의 경우의 수

가로(0) 세로(1) 대각선(2)

현재 위치 (cy, cx)에 특정 방향의 파이프를 놓기 위해,
이전 위치 (py, px)에서 올 수 있는 경우들을 역으로 계산합니다.
이때 파이프의 방향에 따라 올 수 없는 이전 방향은 제외합니다. (exclude)

• 가로(0): 세로(1) 방향의 파이프는 제외
• 세로(1): 가로(0) 방향의 파이프는 제외
• 대각선(2): 없음(-1)

파이프를 놓기 위해 필요한 칸들이 모두 비어 있는 경우에만
해당 위치로의 이동을 허용합니다.

이 과정을 모든 칸에 대해 반복해 (n, n)에 도달하는 모든 경우의 수를 구합니다.

코드

val dy = listOf(0, -1, -1)
val dx = listOf(-1, 0, -1)
val exclude = listOf(1, 0, -1)

fun main() {
    val n = readln().toInt()
    val house = Array(n + 1) { BooleanArray(n + 1) }
    val dp = Array(n + 1) { Array(n + 1) { IntArray(3) } }
        .also { it[1][2][0] = 1 }

    for (cy in 1..n) {
        val row = readln().split(" ").map { it.toInt() }

        for (cx in 1..n) {
            house[cy][cx] = row[cx - 1] == 1

            repeat(3) {
                val py = cy + dy[it]
                val px = cx + dx[it]

                if (!house[cy][cx] && !house[cy][px] && !house[py][cx] && !house[py][px]) {
                    dp[cy][cx][it] += dp[py][px].filterIndexed { i, _ -> i != exclude[it] }.sum()
                }
            }
        }
    }

    println(dp[n][n].sum())
}