[백준 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]
}
Author And Source
이 문제에 관하여([백준 1520 - Kotlin] 내리막길), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kldaji/백준-1520-Kotlin-내리막길저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)