백준 1937 욕심쟁이 판다

출처: www.acmicpc.net/problem/1937

분류: DP, DFS

---

접근방식

기본적인 DFS 접근 방식에 DP의 개념을 추가해서 풀 수 있는 문제였습니다.

한 점에서 갈 수 있는 최대 거리(판다의 생존 일 수)를 DFS를 통해 구해나가는 데, 어차피 그 점에서 시작한 결과는 어차피 어디서 와서 시작하든 같기 때문에 다시 탐색할 필요가 없다는 점을 이용합니다.

따라서 일 수를 기록하는 Map크기와 같은 DP를 채워나가면 해결할 수 있었습니다.

 

해결방법

import Foundation

typealias Point = (r: Int, c: Int)
let n = Int(readLine()!)!

var map = [[Int]]()

for _ in 0..<n {
    map.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

var dpMap = [[Int]](repeating: [Int](repeating: 0, count: n), count: n)

var dr = [1, -1, 0, 0]
var dc = [0, 0, 1, -1]

func dfs(_ curr: Point) -> Int {
    guard dpMap[curr.r][curr.c] == 0 else { return dpMap[curr.r][curr.c] }
    dpMap[curr.r][curr.c] = 1
    for d in 0..<4 where 0..<n ~= curr.r + dr[d] && 0..<n ~= curr.c + dc[d] {
        let next = Point(curr.r + dr[d], curr.c + dc[d])
        guard map[next.r][next.c] > map[curr.r][curr.c] else { continue }
        dpMap[curr.r][curr.c] = max(dpMap[curr.r][curr.c], dfs(next) + 1)
    }
    
    return dpMap[curr.r][curr.c]
}

var maxLife = 0
for r in 0..<n {
    for c in 0..<n {
        maxLife = max(maxLife, dfs((r, c)))
    }
}

print(maxLife)

 

 

배운점

전에 비슷한 문제를 풀어봐서 개념은 어렵지 않았는데 역시 구현이 술술 되지는 않았다..