BOJ-1937 욕심쟁이 판다 Swift

문제

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에는 판다가 이동할 수 있는 칸의 수의 최댓값을 출력한다.

내가 푼 풀이

접근방법 1: DFS(시간초과)

일반적인 DFS로 풀어봤다가 같은 경로를 재탐색하게되어 시간초과가 났다(31퍼에서 안오름..)

 

접근방법 2: DFS + DP

DFS로 탐색하면서, 탐색한 경로에 값을 저장해둔다. 다른 출발점에서 탐색할 때, 이미 탐색된 곳이라면 탐색하지 않는다.

예시로 출발점 1에서 탐색한 경로가 (1 - 2 - 3 - 5)라면, 각 도착점에 값을 저장해둔다.

그 다음 출발점 2에서 탐색한다면 (2 - 3 - 5)로 재탐색하게된다.

이는 이전에 1번에서 탐색했고, 2번에서 출발해도 최댓값은 1번에서 출발한 크기 4가 된다.

 

1번 출발점에서 조건에 맞춰 갈 수 있는 모든 지점을 도달했고,

그 지점마다 이동한 칸수가 저장되어 있으므로, 다시 재탐색을 할 필요가 없다.

DP[y][x]: (x,y)지점에서 이동할 수 있는 칸의 최댓값

 

코드로 구현하면 다음과 같다.

import Foundation

// 입력 받기
let n = Int(readLine()!)!
var arr = [[Int]]()
for i in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

// dp[y][x]: (x,y)에서 최대로 이동할 수 있는 수
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
var result = 0

// 상,하,좌,우 4방향
let dx = [0,1,0,-1]
let dy = [1,0,-1,0]

// DFS + DP
// DFS로 깊이 탐색하며, 최대로 이동한 값을 저장한다.
// DP에 저장하는이유: 이미 최대로 이동한 경로를 재탐색 하지 않기 위해서
// 예시) (1 - 2 - 3 - 4)로 이동한게 최대라면, 2번에서 이동경로는 (2 - 3 - 4)를 갖게된다.
// 2번에서 이동한 경로는 이미 탐색된 경로이므로 굳이 다시 탐색하지않아도된다. (가지치기)
func dfs(_ x: Int,_ y: Int) -> Int {
    // 이미 이동했던 경로라면 종료
    if dp[y][x] != 0 { return dp[y][x] }
    // 이동했던 경로로 표시
    dp[y][x] = 1
    // 네방향으로 조건에 맞춰서 이동
    for k in 0..<dx.count {
        let mx = x + dx[k]
        let my = y + dy[k]
        if (mx >= 0 && mx < n) && (my >= 0 && my < n) {
            if arr[my][mx] > arr[y][x] {
                dp[y][x] = max(dp[y][x], dfs(mx, my) + 1)
            }
        }
    }
    return dp[y][x]
}
// 모든 시작점에서 출발해보고, 최댓값을 구한다.
for i in 0..<n {
    for j in 0..<n {
        result = max(result, dfs(j, i))
    }
}
print(result)