[백준] 1520 내리막 길

 

문제

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

 

입력

n, m = 지도의 행 , 열 길이 
arr: [[Int]] = 각 지점의 높이

결과

ans: Int = 이동 가능한 총 경로 수

해석

내리막길인지 판별한후 dfs를 통해 목적지에 도달 후 return을 통해 카운팅을 해주자.

 

 

코드

import Foundation

let nm = readLine()!.components(separatedBy: " ").map{Int($0)!}

let (n,m) = (nm[0], nm[1])

var arr: [[Int]] = []

for _ in 0..<n {
    arr.append(readLine()!.components(separatedBy: " ").map{Int($0)!})
}

var cache: [[Int]] = [[Int]](repeating: [Int](repeating: -1, count: m), count: n)

let dx = [0,0,-1,1]
let dy = [1,-1,0,0]

func dfs(_ x: Int,_ y: Int) -> Int {
    
    if x == n-1 && y == m-1 {
        cache[x][y] = 1
        return 1
    }
    
    if cache[x][y] != -1 { // 이전에 도착한 기록이 있음
        return cache[x][y]
    }
    
    cache[x][y] = 0
    
    for i in 0..<4 {
        let nx = x + dx[i]
        let ny = y + dy[i]
        
        if !(0..<n ~= nx) || !(0..<m ~= ny) { continue }
        
        // 내리막길이 아님
        if arr[x][y] <= arr[nx][ny] { continue }
        
        // 내리막길이므로 다음으로 구간으로
        cache[x][y] += dfs(nx, ny)
        
    }
    
    return cache[x][y]
    
}

print(dfs(0, 0))