[Kotlin] BOJ1890 점프

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

1890번: 점프

해당 문제에서 주어진 map 사이즈가 100 * 100이고,

주어진 간선도 거의 노드당 2개씩이라고 감안하고 본다면,

인접리스트의 시간복잡도 O(V+E)라고 생각해보면

최대 연산 수가 100 * 100 + 2 * (100 * 100) == 3만

이라고 생각해서 1억에 상당히 못미치는 수기 떄문에

시간복잡도는 BFS돌리기에 충분하다는 생각에 BFS로 접근해서 풀었다.

 

하지만 메모리 초과가 나왔는데

추측건데 아래의 이유가 원인이지 않을까 생각해 봤다.

 

상당히 BFS스러운 문제지만 BFS로 풀면 메모리 초과가 나온다.

 

이유는

보통 BFS로 풀이가 가능한 문제들에서는 현재 Node 근방에 연결된 Node에서

약간 곰팡이가 퍼지듯 주변 노드를 탐색하는 방식(상,하,좌,우 탐색)으로 탐색이 되는데

이런식으로 탐색을 하다보면 무조건 재방문하는(겹치는 탐색 부분) 노드가 생긴다.

그래서 재방문을 막고자 각 Node를 방문한 뒤, isVisited와 같은 배열에

방문 여부를 체크해 둠으로써 중복된 방문을 방지하는 방식으로 풀이된다.

이렇게 하면 지금 문제에서 주어진 100 * 100 사이즈의 map이라도 풀이가 가능한

문제들도 많다.

심지어 토마토 문제는 100 * 100 * 100 사이즈인데도 BFS로 풀린다.

(https://www.acmicpc.net/problem/7569)

하지만 이 문제에서 정답으로 원하는 값은

"가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수"

즉, 같은 Node를 밟았다 하더라도 현재 Node 이전에

어떤 Node를 밟았는지에 따라 다른 경우로 여겨지기 때문에

isVisited와 같은 배열에 방문 여부를 체크하고, 재방문을 막아서는 안된다.

 

그래서 이번 문제에서 BFS를 사용하려면 그냥 중복방문을 다 포함하면서

가장 오른쪽 아래 칸에 도달하는 수를 count하는 방식으로 풀 수 밖에 없는데.

map의 사이즈가 작은경우라면 문제가 되지 않지만,

만약 모든 칸에 값이 1이고, 100 * 100 사이즈의 Map이라면

과장 좀 보태서 Queue에 2^N에 가까운 너무 많은 Node가 들어가기 때문에

(같은 칸의 Node도 중복되게 포함되어 있음으로)

메모리 초과가 나는 것으로 보인다.

 

그래서 재방문을 막을 수 있는 DP + DFS 조합으로 풀거나,

아예 DP식 풀이로 접근하는게 옳은 접근으로 보인다.

 

+ 오른쪽과 아래로 이동할 수 밖에 없다는 조건이 보이면

BFS 말고 DP로도 풀 수 있지 않을까? 하는 생각을

가져보도록 해야겠다.

=============================================================================

혹시 위 내용에 잘못된 접근이 있다면 알려주시면 감사하겠습니다 : )

 

소스코드 (DP)

---

import java.io.BufferedReader
import java.io.FileInputStream
import java.io.InputStreamReader

private var N = 0 //판의 크기 N (4 ≤ N ≤ 100)
private lateinit var map: Array<IntArray>
private lateinit var dp: Array<LongArray>
private fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    N = br.readLine().toInt()
    map = Array(N) { IntArray(N) }
    dp = Array(N) { LongArray(N) }
    repeat(N) { i ->
        map[i] = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    }
    dp[0][0] = 1

    for (y in 0 until N) {
        for (x in 0 until N) {
            if (map[y][x] == 0 || dp[y][x] == 0L) continue
            val nY = y + map[y][x]
            if (isInMap(nY)) {
                dp[nY][x] += dp[y][x]
            }
            val nX = x + map[y][x]
            if (isInMap(nX)) {
                dp[y][nX] += dp[y][x]
            }
        }
    }
    println(dp[N - 1][N - 1])
}

private fun isInMap(p: Int) = (p in 0 until N)