•
•
문제 설명 : 위치마다 숫자가 설정된 grid에서 좌측 최상단 부터 우측 최상단까지 아래/오른쪽만으로 이동할 때, 지나온 경로의 합산 값이 가장 적은 경우를 반환한다.
•
풀이 방법
◦
DP를 사용하여 문제를 풀었다.
◦
좌측 최상단 좌표까지의 최단 경로는 고정이기 때문에, 해당 값을 시작으로 특정 좌표의 최단 값을 찾는 점화식을 사용하였다.
•
시간복잡도 :
•
성공 코드
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
min_sum_grid = [[None] * len(grid[0]) for _ in range(len(grid))]
min_sum_grid[0][0] = grid[0][0]
def search_min_sum(x, y):
if min_sum_grid[x][y] != None:
return min_sum_grid[x][y]
if x == 0 and y > 0:
min_sum_grid[x][y] = search_min_sum(x, y - 1) + grid[x][y]
elif y == 0 and x > 0:
min_sum_grid[x][y] = search_min_sum(x - 1, y) + grid[x][y]
else:
min_sum_grid[x][y] = min(
search_min_sum(x, y - 1) + grid[x][y],
search_min_sum(x - 1, y) + grid[x][y]
)
return min_sum_grid[x][y]
return search_min_sum(len(grid) - 1, len(grid[0]) - 1)
Python
복사
•
더 빠른 코드
결국에는 재귀 동작의 흐름을 보면, 모두 가장자리를 따라가는 것을 알 수 있다.
즉, 우측 맨 아래에서 좌측 맨 상단까지 벽을 따라가는 방식이라는 것이다.
그렇다면, 출발 지점과 연결된 가장자리 라인은 바로 구할 수 있기 때문에 미리 구해놓고 굳이 재귀 없이 for문으로도 빠르게 처리 가능하다.
큰 차이는 아닐 수 있지만, 더 최적화가 가능하여 작성해보았다.
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
min_sum_grid = [[None] * len(grid[0]) for _ in range(len(grid))]
min_sum_grid[0][0] = grid[0][0]
for i in range(1, len(grid[0])):
min_sum_grid[0][i] = min_sum_grid[0][i - 1] + grid[0][i]
for i in range(1, len(grid)):
min_sum_grid[i][0] = min_sum_grid[i - 1][0] + grid[i][0]
for i in range(1, len(grid[0])):
for j in range(1, len(grid)):
min_sum_grid[j][i] = min(
min_sum_grid[j][i - 1] + grid[j][i],
min_sum_grid[j - 1][i] + grid[j][i]
)
return min_sum_grid[-1][-1]
Python
복사