[LeetCode] 64번 - Minimum Path Sum [Swift]

문제 링크

Minimum Path Sum - LeetCode

문제

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

 

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7 Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]] Output: 12

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

문제 풀이

이 문제는 주어진 2차원 배열에서 (0,0)에서 (m-1,n-1)로 가는 경로 중 만나는 모든 값들의 합이 가장 작은 경우를 구하는 문제입니다.

이 문제는 DFS, BFS로 접근 하려고 생각하실 수도 있는데 n,m이 각각 최대 200이므로 경우의수가 정말 너무 많아 시간초과가 발생하게 됩니다.

따라서 저는 DP로 접근했어요.

주어진 2차원 배열 크기랑 동일한 크기의 2차원 배열을 하나 만들고 각 요소마다 해당 칸에 도착하는 최소값을 저장해주시면 됩니다.

위와 같이 0행, 0열에는 해당 위치에 도착하는 방법이 한 가지 방법 뿐이므로 그냥 계속 더해줘야하구요, 그 외의 위치에는 위의 값과 해당 위치의 값을 더한 값, 왼쪽 값과 해당 위치의 값을 더한 값 중 더 작은 값을 저장해주면 됩니다.

이렇게 배열을 계속 채워나간뒤 (m-1, n-1)위치의 값을 반환해주시면 됩니다!

소스 코드

class Solution {
    func minPathSum(_ grid: [[Int]]) -> Int {
        let m = grid.count
        let n = grid[0].count
        var result: [[Int]] = [[Int]](repeating: [Int](repeating: 0, count: n), count: m)
        
        for i in 0..<m {
            for j in 0..<n {
                if i == 0 && j == 0 {
                    result[i][j] = grid[i][j]
                } else if i == 0 {
                    result[i][j] = result[i][j-1] + grid[i][j]
                } else if j == 0 {
                    result[i][j] = result[i-1][j] + grid[i][j]
                } else {
                    result[i][j] = min(result[i-1][j] + grid[i][j], result[i][j-1] + grid[i][j])
                }
            }
        }
        return result[m-1][n-1]
    }
}