64. Minimum Path Sum

Minimum Path Sum - LeetCode

1. Stack을 이용한 DFS(TLE)

from typing import *


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        answer = float("inf")
        s_x, s_y = 0, 0
        t_x, t_y = len(grid) - 1, len(grid[0]) - 1
        height, width = t_x + 1, t_y + 1
        stack = [(s_x, s_y, grid[0][0])]
        visited = [[float("inf")] * width for _ in range(height)]
        visited[0][0] = grid[0][0]
        while stack:
            cur_x, cur_y, cur_length = stack.pop()
            if (cur_x, cur_y) == (t_x, t_y):
                answer = min(answer, cur_length)
                continue
            else:
                if not visited:
                    visited[cur_x][cur_y] = cur_length
                else:
                    if visited[cur_x][cur_y] < cur_length:
                        continue
            left_x, left_y = cur_x, cur_y + 1
            if 0 <= left_x < height and 0 <= left_y < width:
                stack.append((left_x, left_y, cur_length + grid[left_x][left_y]))
            down_x, down_y = cur_x + 1, cur_y
            if 0 <= down_x < height and 0 <= down_y < width:
                stack.append((down_x, down_y, cur_length + grid[down_x][down_y]))

        return answer

Stack을 이용하면 재귀를 사용하지 않고 DFS를 구현할 수 있다. 모든 경로를 탐색하는 풀이기 때문에 시간 초과가 났다.

 

2. Dijkstra

from typing import *
from heapq import *


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        t_x, t_y = len(grid) - 1, len(grid[0]) - 1
        height, width = t_x + 1, t_y + 1
        dist = [[float("inf")] * width for _ in range(height)]
        dist[0][0] = 0
        # 마지막에 시작점 dist 더해야함
        q = [(0, 0, 0)]
        while q:
            cur_length, cur_x, cur_y = heappop(q)
            if dist[cur_x][cur_y] < cur_length:
                continue
            r_x, r_y = cur_x, cur_y + 1
            if 0 <= r_x < height and 0 <= r_y < width:
                new_length = cur_length + grid[r_x][r_y]
                if dist[r_x][r_y] > new_length:
                    dist[r_x][r_y] = new_length
                    heappush(q, (new_length, r_x, r_y))

            d_x, d_y = cur_x + 1, cur_y
            if 0 <= d_x < height and 0 <= d_y < width:
                new_length = cur_length + grid[d_x][d_y]
                if dist[d_x][d_y] > new_length:
                    dist[d_x][d_y] = new_length
                    heappush(q, (new_length, d_x, d_y))
            # for item in dist:
            #     print(item)
            # print()
        return dist[t_x][t_y] + grid[0][0]

최단거리 알고리즘 중 하나인 Dijkstra를 이용해 해결했다.

일반적으로 그래프에서 사용하지만 2차원 배열에서도 사용할 순 있다.

시작점(0,0)에서 목표점(heigth-1, width-1)까지의 최단 경로의 거리를 구하고 마지막에 grid [0][0]을 더한 값을 반환했다.