[백준 1520 - Kotlin] 내리막길

문제링크

• dp[i][j]는 (i, j)에서 목적지 (m-1, n-1)로 갈 수 있는 경로의 개수입니다.
• 따라서 dfs를 실행하면서 목적지에 도착했다면 1을 반환해주고,
• 이미 경로를 구한 좌표에 도착했다면 해당 경로를 반환해줍니다.

import java.io.BufferedReader
import java.io.BufferedWriter

private lateinit var bufferedReader: BufferedReader
private lateinit var bufferedWriter: BufferedWriter
private lateinit var map: MutableList<List<Int>>
private lateinit var dp: Array<Array<Int>>
val dx = listOf(0, 1, 0, -1)
val dy = listOf(1, 0, -1, 0)

fun main() {
    bufferedReader = System.`in`.bufferedReader()
    bufferedWriter = System.out.bufferedWriter()

    // 1. get (m, n)
    val (m, n) = bufferedReader
        .readLine()
        .split(" ")
        .map { it.toInt() }

    map = mutableListOf()
    for (i in 0 until m) {
        map.add(bufferedReader.readLine().split(" ").map { it.toInt() })
    }

    dp = Array(m) { Array(n) { -1 } }
    dfs(0, 0, m, n)
    bufferedWriter.write("${dp[0][0]}")

    bufferedReader.close()
    bufferedWriter.close()
}

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

    // already find
    if (dp[y][x] != -1) return dp[y][x]

    // visit first
    dp[y][x] = 0

    // traverse
    for (i in 0..3) {
        val ny = y + dy[i]
        val nx = x + dx[i]
        if (ny !in 0 until m || nx !in 0 until n) continue

        // lower height
        if (map[ny][nx] < map[y][x]) {
            dp[y][x] += dfs(ny, nx, m, n)
        }
    }
    return dp[y][x]
}