[2023-05-06] 1890 점프 (Kotlin) + 6문제

 

문제 링크: https://www.acmicpc.net/problem/1890

1890번: 점프

 

처음 보자마자 BFS 유형으로 생각하고 문제를 풀었다.

 

 

첫 번째 시도 (메모리 초과)

 

package thirtysixth
import java.io.*
import java.util.*

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    
    // 입력을 저장할 배열
    val location = Array(n){Array(n){0} }
    
    // 방문 배열
    val visit = Array(n){Array(n){false} }
    
    // 입력
    repeat(n){
        val token = StringTokenizer(br.readLine())
        for (index in 0 until n){
            location[it][index] = token.nextToken().toInt()
        }
    }
    
    // 현재 위치
    var curPosition = Pair(0,0) // first = y, second = x

    val queue = LinkedList<Pair<Int,Int>>()
    queue.add(curPosition)
    var count = 0L
	
    
    while(queue.isNotEmpty()){
    
        for (index in queue.indices){
            val first = queue.poll()
            if (!visit[first.first][first.second]){
				
                if (first.first == n-1 && first.second == n-1){
                    count ++
                    continue
                }
                else
                    visit[first.first][first.second] = true

                val locationValue = location[first.first][first.second]

				// 오른쪽, 밑으로 이동 시 배열을 초과하지 않을 경우
                // queue에 추가
                if (first.first + locationValue <= n-1){
                    queue.add(Pair(first.first+locationValue, first.second))
                }

                if (first.second + locationValue <= n-1){
                    queue.add(Pair(first.first, first.second + locationValue))
                }

            }
        }
    }
    println(count)
}

 

 

메모리 초과가 떴습니다.  이를 해결하기 위해서는 방문 조건을 확실하게 설정해야 했지만,

 

방법을 찾지 못해 풀지 못했습니다.

 

지금 생각해 보니, 위의 코드에서는 locationValue 가 0일 경우를 고려를 안 했었네요.

 

 

문제 유형이 DP라는 것을 확인했고, DP로 풀었습니다.

 

 

 

두 번째 시도 (맞았습니다.)

 

package thirtysixth
import java.io.*
import java.util.*

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val location = Array(n){Array(n){0} }
    
    // 땅을 밟은 횟수를 저장할 DP 배열
    val dp = Array(n){Array(n){0L}}

    repeat(n){
        val token = StringTokenizer(br.readLine())
        for (index in 0 until n){
            location[it][index] = token.nextToken().toInt()
        }
    }
	
    // 가장 처음 장소는 한 번 밟았으므로 1L로 초기화
    dp[0][0] = 1L
    
    for (y in 0 until n){
        for (x in 0 until n){
        	
            val locationValue = location[y][x]
            // locationValue가 0 이거나 끝에 도달했을 경우 continue
            if (locationValue == 0 || (y == n-1 && x == n-1) )
                continue
                
            // 오른쪽, 밑으로 이동하는 경우, 배열을 초과하지 않았다면
           	// 이전 dp값을 더해줌
            if (locationValue + x <= n-1)
                dp[y][locationValue + x] += dp[y][x]
            if (locationValue + y <= n-1)
                dp[locationValue+y][x] += dp[y][x]
        }
    }
    println(dp[n-1][n-1])
}