Daily LeetCode Challenge - 64. Minimum Path Sum

Problem From.
https://leetcode.com/problems/minimum-path-sum/

오늘 문제는 맨 왼쪽 위의 출발점에서 시작하여 오른쪽 또는 아래로만 가서 오른쪽 맨 아래 블럭까지 가면서 있는 숫자를 모두 더할때, 그 최소값을 반환하는 문제였다.

처음에는 BFS 로 풀려고 하였으나 시간초과 오류가 나서 다시 한번 생각해본 뒤, DP 로 풀 수 있다는 결론에 도달했다.
문제의 제약조건에 따르면 오른쪽 또는 아래로만 움직일 수 있으므로, 한 블럭을 생각했을때, 그 블럭은 무조건 위나 왼쪽에서 더해진 값들이 오는것이 된다. 그러므로 일단 맨 위와 맨 왼쪽의 값들을 차례차례 더해서 각 칸들의 증가값을 다 구해두고, 안쪽 블럭들의 값을 구할때, 왼쪽과 위의 값중 더 작은 값을 가져와서 블럭들에 누적시켜나가면, 맨 마지막에 도달하는 블럭에 최소값만 쌓이게 된다.

class Solution {
    fun minPathSum(grid: Array<IntArray>): Int {
        for (i in 1..grid.lastIndex) {
            grid[i][0] = grid[i-1][0] + grid[i][0]
        }
        for (j in 1..grid.last().lastIndex) {
            grid[0][j] = grid[0][j-1] + grid[0][j]
        }
        
        for (i in 1..grid.lastIndex) {
            for (j in 1..grid.last().lastIndex) {
                grid[i][j] = minOf(grid[i-1][j], grid[i][j-1]) + grid[i][j]
            }
        }
        
        return grid[grid.size - 1][grid[0].size - 1]
    }
}