백준 2169 로봇 조종하기

출처: https://www.acmicpc.net/problem/2169

분류: DP

---

접근방식

백트래킹 문제 같이 보이지만, n, m이 최대 1000이기 때문에 백트래킹으로 접근하면 시간초과가 납니다.

백트래킹에 복잡도를 생각해봤는데, 한 번 이동마다 최대 3가지 경로로 가지가 쳐지고
위로 이동은 없으니 거꾸로 경우를 줄여 2가지로 잡아도 2^1000 하면 시간초과를 면치 못한다고 생각이 드는데요, 
제대로 판단한건지는 잘 모르겠네요... 정확히 아시는 분은 답글 부탁드립니다 🙇🏻‍♂️

 

이 문제는 DP로 접근해서 해결할 수 있는데요,

위로 이동하는 경우는 없으니 맨 윗줄은 1, 1지점부터 오른쪽으로 이동하는 경우가 최선의 경우입니다.

for col in 1..<m {
    dpMap[0][col] = dpMap[0][col-1] + map[0][col]
}

 

그 다음부터는 일반화해서 생각해야하는데요,
위는 이미 최적화 되어있으니 왼쪽에서 오는 경우와 오른쪽에서 오는 경우를 각각 구해서 최대를 선택해주면 됩니다.

주의해야 할 점은 왼쪽, 오른쪽을 각각 구해서 결과를 가지고 비교하지 않으면 케이스가 뒤섞이므로 제대로 된 값을 구할 수 없습니다!

for row in 1..<n {
    // from left
    dpMap[row][0] = dpMap[row-1][0] + map[row][0]
    for col in 1..<m {
        dpMap[row][col] = max(dpMap[row-1][col] + map[row][col], dpMap[row][col-1] + map[row][col])
    }
    
    // from right
    guard row < n-1 else { break }
    var temp = [Int](repeating: 0, count: m)
    temp[m-1] = dpMap[row-1][m-1] + map[row][m-1]
    for col in (0..<m-1).reversed() {
        temp[col] = max(dpMap[row-1][col] + map[row][col], temp[col+1] + map[row][col])
    }
    
    for col in 0..<m {
        if temp[col] > dpMap[row][col] {
            dpMap[row][col] = temp[col]
        }
    }
}

 

맨 마지막 줄은 왼쪽부터 오는 경우만 확인해주면 되니까 guard로 처리해줬습니다.

 

해결방법

typealias Point = (row: Int, col: Int)
let moving = [[1, 0], [0, -1], [0, 1]]
let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, m) = (nm[0], nm[1])
var map = [[Int]]()
for _ in 0..<n {
    map.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

var dpMap = [[Int]](repeating: [Int](repeating: 0, count: m), count: n)
dpMap[0][0] = map[0][0]
for col in 1..<m {
    dpMap[0][col] = dpMap[0][col-1] + map[0][col]
}

for row in 1..<n {
    // from left
    dpMap[row][0] = dpMap[row-1][0] + map[row][0]
    for col in 1..<m {
        dpMap[row][col] = max(dpMap[row-1][col] + map[row][col], dpMap[row][col-1] + map[row][col])
    }
    
    // from right
    guard row < n-1 else { break }
    var temp = [Int](repeating: 0, count: m)
    temp[m-1] = dpMap[row-1][m-1] + map[row][m-1]
    for col in (0..<m-1).reversed() {
        temp[col] = max(dpMap[row-1][col] + map[row][col], temp[col+1] + map[row][col])
    }
    
    for col in 0..<m {
        if temp[col] > dpMap[row][col] {
            dpMap[row][col] = temp[col]
        }
    }
}

print(dpMap[n-1][m-1])

 

혹시 참고삼아 백트래킹 풀이도 남겨봅니다....

// 백트래킹 시간초과

var visit = [[Bool]](repeating: [Bool](repeating: false, count: m), count: n)
func explore(at point: Point) -> (Int, Bool) {
    let currentCost = map[point.row][point.col]
    var maxCost = currentCost
    var sendFromEnd = point.row == n-1 && point.col == m-1

    for move in moving {
        let nr = point.row + move[0], nc = point.col + move[1]
        guard nr >= 0, nr < n, nc >= 0, nc < m, !visit[nr][nc] else { continue }
        visit[point.row][point.col] = true
        let (cost, fromEnd) = explore(at: (nr, nc))
        if fromEnd {
            sendFromEnd = fromEnd
            maxCost = max(maxCost, currentCost + cost)
        }
        visit[point.row][point.col] = false
    }


    return (maxCost, sendFromEnd)
}

print(explore(at: (0, 0)).0)

 

배운점

힘내자 힘!!