[백준] 내리막 길 (1520)(kotlin)

문제 설명

백준 1520번 문제 링크

입력 및 출력

» 입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

» 출력

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

예제 입출력(테스트케이스)

입력	출력
4 5 50 45 37 32 30 35 50 40 20 25 30 30 25 17 28 27 24 22 15 10	3

문제 풀이1

풀이 참고

val dx = intArrayOf(0, 1, 0, -1)
val dy = intArrayOf(1, 0, -1, 0)
var dp = arrayOf<IntArray>()
var route = arrayOf<IntArray>()

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    val (m, n) = readLine().split(" ").map { it.toInt() }

    route = Array(m) {
        readLine().split(" ").map { it.toInt() }.toIntArray()
    }
    dp = Array(m) {
        IntArray(n) { -1 }
    }

    println(dfs(m, n, 0, 0))
}

fun dfs(m: Int, n: Int, y: Int, x: Int): Int {
    if (y == m - 1 && x == n - 1) {
        return 1
    }

    if (dp[y][x] != -1) {
        return dp[y][x]
    }

    dp[y][x] = 0
    for (i in 0 until 4) {
        val nx = x + dx[i]
        val ny = y + dy[i]

        if (nx !in 0 until n || ny !in 0 until m) continue
        if (route[y][x] > route[ny][nx]) {
            dp[y][x] += dfs(m, n, ny, nx)
        }
    }

    return dp[y][x]
}