백준 1937번 욕심쟁이 판다 - 스위프트(Swift) 풀이

---

 

1. dp(row, col) = (row, col)에서 시작했을 때 이동할 수 있는 최대 칸수
2. dp(row, col) = max(1 + dp(상하좌우))

 

1. dp(row, col) = (row,col)에서 시작했을 때 이동할 수 있는 최대 칸수

 dp(row, col)을 위와 같이 정의할 것이다.

 

2. dp(row, col) = max(1 + dp(상하좌우))

 인접한 상하좌우 중 어떤 칸으로 이동했을 때 가장 많은 칸을 이동할 수 있는지 모두 따져본다. 만약 오른쪽 칸에 현재 칸보다 더 많은 대나무가 있다면 이동할 수 있고, 현재 칸에서 오른쪽으로 가는 방법을 선택했을 때 이동할 수 있는 최대 칸수는 1 + dp(row, col+1)이 된다. 이렇게 상하좌우 네 칸에 대해 모두 대나무가 더 많은지 체크하고, 더 많다면 해당 칸으로 이동할 수 있으므로 고려해준다음 max값을 취하면 된다. 상하좌우에 더 적은 대나무만 있는 경우 더 이상 dp 호출이 일어나지 않기 때문에 이 경우가 자동적으로 기저 사례가 된다.

반응형

---

import Foundation

var N = 0
var forest = Array(repeating: [Int](), count: 500)
var cache = Array(repeating: Array(repeating: -1, count: 500), count: 500)

func dp(row: Int, col: Int) -> Int {
    var ret = cache[row][col]
    if ret != -1 { return ret }
    
    ret = 1
    let adjacents = [(row-1,col), (row+1,col), (row,col-1), (row,col+1)].filter {
        (0..<N) ~= $0.0 && (0..<N) ~= $0.1
    }
    for adj in adjacents {
        guard forest[adj.0][adj.1] > forest[row][col] else { continue }
        ret = max(ret, 1 + dp(row: adj.0, col: adj.1))
    }
    
    cache[row][col] = ret
    
    return ret
}

func solution() {
    N = Int(readLine()!)!
    
    for i in 0..<N {
        forest[i] = readLine()!.split(separator: " ").map{ Int(String($0))! }
    }
    
    var maxMove = 0
    for i in 0..<N {
        for j in 0..<N {
            maxMove = max(maxMove, dp(row: i, col: j))
        }
    }
    print(maxMove)
}

solution()