[백준] 1520번 내리막길
문제
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.
현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.
지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.
접근방법
DP + DFS를 이용해서 풀었다.
즉 다시 말해 이미 [height, width]로 탐색을 했던 길이라면 탐색하지 않고 값을 반환하여 사용한다.
처음엔 BFS로 접근하였는데, 메모리초과로 실패
따라서 DP를 이용해야 한다고 생각함.
처음에는 return DP[height][width]로 하려했는데 그럴 경우 위로가는 경우, 좌로 가는 경우에 놓치는 경우가 생겼다.
따라서 DP[y][x]를 y,x에서 height, width로 가는 경우의수로 정의하여 1,1로 경우의 수가 수렴하는 방식으로 접근하여 풀이하였다.
코드
class IO1520 {
private val br = System.`in`.bufferedReader()
private val bw = System.out.bufferedWriter()
fun getHeightAndWidth() = br.readLine().split(" ").map { it.toInt() }
fun getRow() = br.readLine().split(" ").map{ it.toInt() }
fun flush() = bw.flush()
fun close() = bw.close()
fun write(message: String) = bw.write(message)
}
fun main() {
val io = IO1520()
val (height, width) = io.getHeightAndWidth()
val dx = arrayOf(-1,1,0,0)
val dy = arrayOf(0,0,-1,1)
val graph = Array(height) { Array (width) { -1 } }
val dp = Array(height) { Array (width) { -1 } }
repeat(height) {
io.getRow().forEachIndexed { idx, h ->
graph[it][idx] = h
}
}
fun dfs(y: Int, x: Int): Int {
if ( y == height -1 && x == width -1) {
return 1
}
if (dp[y][x] != -1) return dp[y][x]
else dp[y][x] = 0
dy.forEachIndexed { idx, cy ->
val nx = dx[idx] + x
val ny = cy + y
if (nx in 0 until width && ny in 0 until height && graph[y][x] > graph[ny][nx]) {
dp[y][x] += dfs(ny, nx)
}
}
return dp[y][x]
}
io.write(dfs(0,0).toString())
io.flush()
io.close()
}
Author And Source
이 문제에 관하여([백준] 1520번 내리막길), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@greenddoovie/백준-1520번-내리막길저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)