[LeetCode] 64. Minimum Path Sum (Swift, Python)

Minimum Path Sum - LeetCode

 

풀이

 (0, 0)에서 출발하여 (m-1, n-1)까지 갈 때 grid에 적혀 있는 숫자의 합이 최솟값이 되는 경우를 찾는 문제. 간단하게 bfs를 사용해서 문제를 풀었는데 다른 사람들의 속도를 보니 dp를 활용하여 문제를 해결할 수 있는 것 같다. 추후에 dp에 대해서 공부할 때 다시 한 번 풀어봐야겠다.

 

코드

[Swift]

typealias queueElement = (cost: Int, x: Int, y: Int)
 
class Solution {
    func minPathSum(_ grid: [[Int]]) -> Int {
        let m: Int = grid.count
        let n: Int = grid[0].count
        var ans: Int = Int.max
        
        let dx: [Int] = [0, 1]
        let dy: [Int] = [1, 0]
        
        var flag: [[Bool]] = Array(repeating: Array(repeating: false, count: n), count: m)
        
        var q: [queueElement] = [(grid[0][0], 0, 0)]
        flag[0][0] = true
        
        while !q.isEmpty {
            q.sort(by: { $0.cost < $1.cost })
            let qHead: queueElement = q.removeFirst()
            
            if qHead.x == m-1 && qHead.y == n-1 {
                ans = qHead.cost
                break
            }
            
            for i in 0..<2 {
                let nx: Int = qHead.x + dx[i]
                let ny: Int = qHead.y + dy[i]
                
                if nx >= m || ny >= n || flag[nx][ny] {
                    continue
                }
                
                q.append((qHead.cost + grid[nx][ny], nx, ny))
                flag[nx][ny] = true
            }
        }
        
        return ans
    }
}
 

 

[Python]

import heapq
 
class Solution(object):
    def minPathSum(self, grid):
        m = len(grid)
        n = len(grid[0])
 
        dx = [0, 1]
        dy = [1, 0]
 
        flag = [[False] * n for _ in range(m)]
 
        q = []
        heapq.heappush(q, (grid[0][0], 0, 0))
        flag[0][0] = True
 
        while True:
            cost, x, y = heapq.heappop(q)
 
            if x == m-1 and y == n-1:
                return cost
            
            for i in range(2):
                nx = x + dx[i]
                ny = y + dy[i]
 
                if nx >= m or ny >= n or flag[nx][ny]:
                    continue
                
                heapq.heappush(q, (cost+grid[nx][ny], nx, ny))
                flag[nx][ny] = True