[Swift][DP] 백준 11048번 (이동하기)

요구능력 : DP문제 인식능력

 

코드설명 : 

 

이 문제는 BFS로도 풀릴거 같긴한데 고생의 지름길이다.

 

DP로 접근할 수 있는 이유는 나는 개인적으로 예제 입력 1을 그려보고 갈 수 있는 방향을 그려보니 문제에서 주어진 방향으로만 이동해도 한 좌표에 모든경우의 수가 들어와서 좌표에 들어오는 값들중에 max값을 저장하면 되겠다고 생각했다.

 

 

후기 : BFS로 접근하고 풀어보다가 시간초과까지는 해결했는데 메모리초과까지 나버려서 포기하고 DP로 풀어야겠다생각하니까 답이 금방나와버렸다.. 뭔가 나처럼 처음접근은 거의다 BFS로 하실듯..?

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]

var arr = [[Int]]()
for _ in 0..<n{
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}
var dp = Array(repeating: Array(repeating: 0, count: 1001), count: 1001)
dp[0][0] = arr[0][0]
for r in 0..<n{
    for c in 0..<m{
        if r >= 0 && r < n && c + 1 < m {
            dp[r][c + 1] = max(dp[r][c + 1], dp[r][c] + arr[r][c + 1])
        }
        if r + 1 < n {
            if c >= 0{
                dp[r + 1][c] = max(dp[r + 1][c], dp[r][c] + arr[r + 1][c])
            }
            if c + 1 >= 0 && c + 1 < m {
                dp[r + 1][c + 1] = max(dp[r + 1][c + 1], dp[r][c] + arr[r + 1][c + 1])
            }
        }
    }}
print(dp[n - 1][m - 1])