PS(Problem Solving)/BOJ

[백준/BOJ] 1520번: 내리막 길

JunsuKim 2022. 8. 8.
728x90

문제

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

 

1520번: 내리막 길

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으

www.acmicpc.net

해설

DFS로만으로 풀려다가 도저히 풀리지 않아 다른 분들이 써놓은 풀이를 참고하였다.

DFS만을 이용하면 시간초과가 나게 되어 DP를 함께 사용하는 방법을 알 수 있었다.

 

각 현재 지점에서 4방향으로 탐색을 한다. 이 때 갈 수 있는 경우의 수를 저장하면서, DFS를 수행하게 된다.

만약 이미 탐색했던 지점이라면, 그 지점에서 갈 수 있는 경로의 수를 반환해준다.

도착 지점에 도착하게 되면 1을 반환하게 해준다.

소스 코드

import java.util.*

private val dx = intArrayOf(1, -1, 0, 0)
private val dy = intArrayOf(0, 0, 1, -1)
private var row = 0
private var col = 0
private lateinit var map: Array<IntArray>
private lateinit var check: Array<IntArray>

fun main() = with(System.`in`.bufferedReader()) {
    var st = StringTokenizer(readLine())
    row = st.nextToken().toInt()
    col = st.nextToken().toInt()

    map = Array(row + 1) { IntArray(col + 1) }
    check = Array(row + 1) { IntArray(col + 1) { -1 } }
    for(i in 1 .. row) {
        st = StringTokenizer(readLine())
        for(j in 1 .. col) {
            map[i][j] = st.nextToken().toInt()
        }
    }

    println(dfs(1, 1))
}

private fun dfs(y: Int, x: Int): Int {
    if(y == row && x == col) return 1

    if(check[y][x] == -1) {
        check[y][x] = 0
        for(i in 0 until 4) {
            val nextY = y + dy[i]
            val nextX = x + dx[i]

            if(nextY !in 1 .. row || nextX !in 1 ..col) continue
            if(map[nextY][nextX] < map[y][x]) check[y][x] += dfs(nextY, nextX)
        }
    }

    return check[y][x]
}
728x90

댓글