[Kotlin][Algorithm] 1890 - 점프

D.O·2024년 3월 13일

알고리즘 코틀린

문제 요약

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 이동할 수 있는 경로의 개수를 구하는 문제

문제접근

dfs

초기에 이 문제는 n이 최대 100으로 간단한 dfs문제로 생각하고 dfs로 풀려고 했다
하지만 메모리 초과가 발생했다.

그 이유는 이 문제는 이 전에 밟았던 블록이 이전 경로가 다르다면 다시 밟아지는 경우 또한 고려해야하기 때문에 visited 처리를 해주지 않는다.

나는 그 점을 인지하고 있었지만 visited를 하지 않는다고 2방향으로 나가는 경우가 메모리 초과가 날 만큼 이렇게 커질줄은 몰랐고 이번 기회로 배웠다.

먼저 visited를 하지 않는다면 시간복잡도는 얼마나 걸릴까?

n은 최대 100이다
방향은 아래쪽과 오른쪽 두방향이다.

그렇다면 시간복잡도는 보편적인 조합론으로 구할 수 있다.
오른쪽으로 가는 선택을 N번, 아래로 가는 선택을 N번 존재 할 때 2n개를 나열하면된다.

물론 방향별로 n개씩 존재하기에 최대 (2N!)/(N!N!) 이 걸립니다. 100을 대입하면 굉장히 큰 수이다.

visited를 하지 않는다면 이렇게 까지 커지는 줄 몰랐다..

dp + dfs

그래서 메모제이션을 도입하였다.
한번 방문한 경로에서 목적지로 도달할 수 있는 경우의 수를 기록해놓았다. 그렇다면 이 문제는 visited를 도입할 수 있는 문제가 된다.

이 문제는 오른쪽과 아래쪽으로만 이동 할 수 있기 때문에 한 진행 방향에서 되돌아올 수 없다.

따라서 다시 그 위치에 방문을 한다면 그 방문은 다른 경로로 방문한 것을 보장한다.

따라서 방문한 곳이라면 이미 구해놓았던 방문의 개수를 이용하면 된다. 어처피 그 위치에서 또 도달할 수 있는 경우는 동일하니..

dp (only)

이 문제는 오직 dp로만으로도 해결이 가능하다.
일단 시작점인 dp[0][0]은 1로 초기화한다.

이전에 언급했듯이 오른쪽 아래쪽으로만 도달하기 때문에
시작점 부터 시작해 점프를 통해 이동할 수 있는 부분에 이전 경로의 수를 더해주면 된다.

(i, j) 위치에 도달하는 경로의 수는 (i - jump, j)와 (i, j - jump) 위치에 도달하는 경로의 수에 의해 결정된다.
그리고 특정 칸으로 이동하는 데 여러 경로가 있을 수 있고, 이 칸을 경유하는 다른 경로들도 비슷하게 중복될 수 있다. 따라서 중복된 하위 문제이므로 DP를 사용하면 각 칸에 도달하는 경로의 수를 한 번만 계산하여 저장함으로써 중복 계산을 방지 할 수 있다.

이 또한 오른쪽,아래쪽으로 이동 가능하므로 한 경로를 통해 도달한 점은 다시 되돌아 올수없다는 것을 보장하기 때문에 가능하다.

코드

dp + dfs


data class Point(val x: Int, val y: Int)

fun main() {
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val arr = Array(n) { br.readLine().split(" ").map { it.toInt() } }
    val visited = Array(n) { BooleanArray(n) }
    val canGo = Array(n) { LongArray(n) }

    val start = Point(0, 0)
    val end = Point(n - 1, n - 1)
    val moveX = arrayOf(0, 1)
    val moveY = arrayOf(1, 0)

    fun dfs(s: Point): Long {
        if (s == end) return 1L
        val (x, y) = s
        visited[x][y] = true
        val moveCount = arr[x][y]
        for (dir in 0 until 2) {
            val moveXCount  = moveX[dir] * moveCount
            val moveYCount  = moveY[dir] * moveCount

            val nx = x + moveXCount
            val ny = y + moveYCount

            if (nx in arr.indices && ny in arr[0].indices) {
                // 방문하지 않은 곳이라면 dfs
                if (!visited[nx][ny]) {
                    val result = dfs(Point(nx, ny))
                    if (result >= 1) canGo[x][y] += result
                } else {
                    // 방문한곳이라면 메모제이션 그대로 이용
                    canGo[x][y] += canGo[nx][ny]
                }
            }
        }

        return canGo[x][y]
    }

    dfs(start)
    println(canGo.first().first())
}

dp (only)


fun main() {
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val arr = Array(n) { br.readLine().split(" ").map { it.toInt() } }
    val dp = Array(n) { LongArray(n) }
    dp[0][0] = 1
    for (i in 0 until n) {
        for (j in 0 until n) {
            // 마지막 점이 아니고 i,j까지 도달할 수 있는 방법이 존재한다면
            val jump = arr[i][j]
            if (jump != 0 && dp[i][j] >= 1) {
                if (j + jump < n) dp[i][j + jump] += dp[i][j]
                if (i + jump < n) dp[i + jump][j] += dp[i][j]
            }
        }
    }

    println(dp.last().last())
}