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

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

 

해당 문제는 DFS의 특징 중 경로를 지나갔는지 기록할 수 있다는 특성을 알고 사용해야 풀 수 있는 문제였습니다.

저의 경우 처음에 문제를 읽고 일반적인 DFS를 이용하여 코드를 작성하였었으나 메모리초과가 발생하여 통과 하지 못하였었습니다. 그리고 원인이 무엇인지 잘 몰라 수정을 계속 하면서 작성하고 있었습니다. 그러던 중 알고리즘 스터디 강의 에서 해당 문제는 DFS의 특성 을 사용해야 한다는 것과 제가 처음에 작성한 코드가 메모리 초과가 되는 원인을 알았습니다. 제가 처음에 작성하였었던 코드는 DFS를 실행하면서 결과값을 +1 하는 코드였는데 문제의 설명 중 "첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다." 라는 문구가 있습니다. 이것은 즉 결과값이 최대 10억까지 나올 수 있다는 라는 말이며, 이 경우 +1 연산을 10억번 이상하게 되어 메모리 초과가 나지 않더라도 시간초과가 날 수 있음을 의미 했습니다. 

제가 아직 공부 부족이라 해당 문구를 보고 답이 Int 범위 이내 라는 것을 말하는 거겠구나 라고만 생각하고 다른 생각을 하지 않아 작성한 코드가 메모리 초과가 나왔던 것입니다.

일반적으로 DFS에서 +1연산은 최대 대략 십만번정도 까지가 시간 초과 및 메모리 초과가 나지 않는 다는 것을 깨닫게 되었습니다.

그리고 해당 문제를 스터디에서 알게 된 DFS의 특성 중 해당 위치를 몇번 갔는지를 기록할 수 있는 특성을 이용하여, 코드를 작성하였습니다.

 

하기코드들을 보시면 첫번째 코드는 일반적인 DFS코드로써 도착지점에 도착하면 결과값에 +1를 하는 코드입니다.

해당 코드는 위에서 말씀드린 것처럼 +1연산을 최대 10억번 할 수 있는 코드라서 시간 초과 및 메모리 초과를 발생 시키는 코드였습니다.

그리고 수정한 코드를 보시면 해당 위치에서 도착지점까지 가는 방법의 수를 visit 배열에 저장하여 시작 위치에서의 도착지점까지의 도착 방법 수를 기록하여 결과 값을 알아내는 것을 확인 할 수 있습니다.

 

 

일반적인 dfs를 사용하여 작성한 코드 및 제출결과입니다. (메모리 초과 발생한 코드)

 

// 메모리 초과 발생 코드

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.lang.Math.max
import java.util.*


var row = intArrayOf(0,0,-1,1)
var col = intArrayOf(-1,1,0,0)

lateinit var miro : Array<ArrayList<Info>>
lateinit var visit : Array<BooleanArray>
var answer = 0
var N = 0
var M = 0


fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    //var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

     miro = Array(N,{ArrayList<Info>()})
     visit = Array(N,{BooleanArray(M){true}})

    repeat(N){
        st = StringTokenizer(br.readLine())
        val index = it
        repeat(M){
            miro[index].add(Info(index,it,st.nextToken().toInt()))
        }
    }
//    miro.forEach {
//        println(it.toMutableList())
//    }

    dfs(Info(0,0,miro[0][0].value))
    println(answer)

    //bw.flush()
    //bw.close()
}

fun dfs(now:Info){
    val nr = now.row
    val nc = now.col
    val nv = now.value
    if(!visit[nr][nc]) return
    visit[nr][nc] = false

    if(nc == M-1 && nr == N-1){
        answer++
        visit[nr][nc] = true
        return
    }

    for(i in 0 .. 3){
        val nextC = col[i]
        val nextR = row[i]
        if(nc+nextC < 0 || nr+nextR < 0 || nc+nextC >= M || nr+nextR >= N) continue
        if(!visit[nr+nextR][nc+nextC]) continue
        if(miro[nr+nextR][nc+nextC].value >= nv) continue
        dfs(Info(nr+nextR,nc+nextC,miro[nr+nextR][nc+nextC].value))
    }
    visit[nr][nc] = true
}

data class Info(
    val row:Int,
    val col:Int,
    val value: Int
)

 

특성을 이용하여 작성한 코드(통과 코드) 및 제출 결과

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.lang.Math.max
import java.util.*


var row = intArrayOf(0,0,-1,1)
var col = intArrayOf(-1,1,0,0)

lateinit var miro : Array<IntArray>
lateinit var visit : Array<IntArray>
var N = 0
var M = 0


fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    //var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

     miro = Array(N,{IntArray(M){0}})
     visit = Array(N,{IntArray(M){-1}})

    repeat(N){
        st = StringTokenizer(br.readLine())
        val index = it
        repeat(M){
            miro[index][it] = st.nextToken().toInt()
        }
    }

    visit[N-1][M-1] = 1
    println(dfs(0,0))

    //bw.flush()
    //bw.close()
}

fun dfs(r:Int,c:Int):Int{
    if(visit[r][c] > -1) return visit[r][c]

    visit[r][c] = 0

    for(i in 0 .. 3){
        val nr = row[i]+r
        val nc = col[i]+c
        if(nr < 0 || nc < 0 || nr >= N || nc >= M) continue
        if(miro[r][c] <= miro[nr][nc]) continue
        visit[r][c] += dfs(nr,nc)
    }

    return visit[r][c]
}


data class Info(
    val row:Int,
    val col:Int
)