728x90
문제
https://www.acmicpc.net/problem/1520
해설
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
'PS(Problem Solving) > BOJ' 카테고리의 다른 글
[백준/BOJ] 11404번: 플로이드 (0) | 2022.08.08 |
---|---|
[백준/BOJ] 11403번: 경로 찾기 (0) | 2022.08.08 |
[백준/BOJ] 4485번: 녹색 옷 입은 애가 젤다지? (0) | 2022.08.07 |
[백준/BOJ] 1261번: 알고스팟 (0) | 2022.08.06 |
[백준/BOJ] 1504번: 특정한 최단 경로 (0) | 2022.08.05 |
댓글