[백준] 1890번: 점프 - Kotlin[코틀린]

문제

 

1890번: 점프

 

---

풀이

 

 문제는 시작점부터 도착점까지 도달 가능한 경로 수를 구하는 것이다. 처음엔 DFS로 시도했지만 시간초과가 발생하여 반복문과 DP를 활용한 풀이를 하였다.

 

 시작점인 dp[0][0]에 1을 할당하고, 반복문을 통해 각 위치까지의 도달 가능한 경로 수를 구한다. dp[i][j]가 0인 배열은 처리하지 않고 넘어가도록 하며 0이 아닌 경우에는 오른쪽과 아래 방향으로 map[i][j]만큼 이동 한 후, 그 지점의 dp 배열에 현재 위치 경로 수를 더해준다.

 

---

코드

 

import java.util.*

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

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

    val num = br.readLine().toInt()
    val map = Array(num){ IntArray(num) }
    val dp = Array(num){ LongArray(num) }

    for(i in 0 until num) {
        val st = StringTokenizer(br.readLine())
        for(j in 0 until num) {
            map[i][j] = st.nextToken().toInt()
        }
    }

    dp[0][0] = 1L

    for(i in 0 until num) {
        for(j in 0 until num) {
            if(i == num - 1 && j == num - 1) continue // 도착 지점은 처리하지 않음
            if(dp[i][j] == 0L) continue // 도달 불가능한 경로

            val jump = map[i][j]
            for(d in 0 until 2) {
                val nx = i + jump*dx[d]
                val ny = j + jump*dy[d]

                if(nx < 0 || ny < 0 || nx >= num || ny >= num) continue

                dp[nx][ny] += dp[i][j] // 경로 수 업데이트
            }
        }
    }

    bw.write("${dp[num-1][num-1]}")
    bw.flush()
    bw.close()
    br.close()
}