[백준 1520번] [Kotlin] 내리막 길

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

 

난이도 : 골드 3
태그 : 다이나믹 프로그래밍, 깊이 우선 탐색, 그래프 이론, 그래프 탐색 

 

 

설명

DFS를 사용해 탐색하는 문제입니다.

다만, M, N이 500 이하의 자연수 이므로 DFS만 사용해서는 시간초과 / 메모리 초과가 발생하며,

다이나믹 프로그래밍 기법이 사용되어야 합니다

 

dp를 -1로 초기화하여 탐색을 하지 않는 공간을 나타냅니다.

DFS를 이용해 탐색하며 이차원 배열 dp에 시작점에서 끝점까지 이동하는 경로를 각각 저장하고,

탐색 도중 이미 만난 지점이라면(dp[x][y] != -1) 해당 지점의 경로의 개수를 return 합니다.

 

 

 

소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

val dx = arrayOf(1, -1, 0, 0)
val dy = arrayOf(0, 0, 1, -1)

lateinit var map: Array<Array<Int>>
lateinit var dp: Array<Array<Int>>

var n = 0
var m = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    val nm = br.readLine().split(" ")
    n = nm[0].toInt()
    m = nm[1].toInt()

    map = Array(n) { Array(m) { 0 } }
    dp = Array(n) { Array(m) { -1 } }

    repeat(n) { x ->
        val st = StringTokenizer(br.readLine())
        repeat(m) { y ->
            map[x][y] = st.nextToken().toInt()
        }
    }
    
    println(dfs(0, 0))
}

fun dfs(x: Int, y: Int):Int {
    if(x == n - 1 && y == m - 1 ) return 1
    if(dp[x][y] != -1) return dp[x][y]

    dp[x][y] = 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 || map[x][y] <= map[nx][ny]) continue

        dp[x][y] += dfs(nx, ny)
    }

    return dp[x][y]
}

 

 

 

후기

처음에 그냥 DFS만 이용해서 풀려 했다가, 메모리 초과로 인해 실패했던 문제였고,

질문게시판을 염탐하며 DP를 사용해야 하는구나... 하며 풀었던 문제였습니다.