Swift) 백준 1937번 욕심쟁이 판다 - G3

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

1937번: 욕심쟁이 판다

 

문제 풀이: dfs와 메모이제이션을 이용하여 푼 문제. dfs로 특정 칸에 있을때 최대로 움직일 수 있는 갯수를 구하여 메모이제이션에 저장, 해당 좌표에 다시 접근하였을때 바로 리턴을 하는 방식으로 문제를 구현. 만약 dfs로만 하게 된다면 시간 초과가 뜨니 메모이제이션은 필수로 구현해야 하는듯 하다.

 

import Foundation

let n = Int(readLine()!)!
var map: [[Int]] = []
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: n), count: n)
let mx = [0,1,0,-1]
let my = [-1,0,1,0]

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

func move(i: Int, j: Int) -> Int {
    if dp[i][j] != 0 {
        return dp[i][j]
    }
    dp[i][j] = 1
    
    for k in 0..<4 {
        let nextI = i+my[k]
        let nextJ = j+mx[k]
        if nextI < 0 || nextI >= n || nextJ < 0 || nextJ >= n {
            continue
        }
        if map[i][j] < map[nextI][nextJ] {
            dp[i][j] = max(dp[i][j], move(i: nextI, j: nextJ)+1)
        }
    }
    return dp[i][j]
}

func solution() {
    var answer = 0
    for i in 0..<n {
        for j in 0..<n {
            answer = max(answer, move(i: i, j: j))
        }
    }
    print(answer)
}

solution()