🧨 문제

양수로 이루어진 m x n 그리드가 인자로 들어 온다.
상단 왼쪽에서 시작하여,
하단 오른쪽까지 가는 길의 요소를 다 더했을 때,
가장 작은 합을 찾아서 return 하라.

한 지점에서 우측이나 아래로만 이동할 수 있다.

Input: [ [1,3,1],   
	 [1,5,1],    
         [4,2,1] 
       ]
Output: 7

1→3→1→1→1 으로 요소의 합이 가장 작음

🏹 발상

(0, 0) 에서 (1, 1) 으로 가는 최소 경로는
(0, 1) 방향과 (1, 0) 방향 중
작은 쪽을 택해 더하는 경우 이다.

(0, 1)에서 (1, 2)로 가는 최소 경로는 (0, 2)와 (1, 1)을 거쳐 오는 경우 중 최소 경로를 택하는 경우이다.

마찬가지로
(1, 0)에서 (2, 1)로 가는 최소 경로는 (1, 1)와 (2, 0)을 거쳐 오는 경우 중 최소 경로를 택하는 경우이다.

계속해서
(1, 1)에서 (3, 2)로 가는 최소 경로는 (2, 1)와 (1,2) 를 거쳐 오는 경우 중 최소 경로를 택하는 경우이다.

이런 방식으로 (0, 0)에서 (x, y)까지의 최소 경로를 누적해 더하면 최소 경로를 구할 수 있다.

재귀 함수, 다이나믹 프로그래밍을 이용해 풀어 보았는데, 풀이 방법의 차이는 있지만, 아이디어는 동일 하다

🎯 내 풀이

(재귀 함수 활용)

def min_path_sum(grid):
   #step1
    first_columns = [element[0] for element in grid]
    
   #step2
    def sum_path(x, y):
        if x == 0 and y == 0:
            return grid[x][y]
        elif x == 0 and y > 0:
            return sum(grid[x][:y+1])
        elif x > 0 and y == 0:
            return sum(first_columns[:x+1]) 
        return min(sum_path(x-1, y), sum_path(x, y-1)) + grid[x][y]
    
    #step3      
    return sum_path(len(grid)-1, len(grid[0])-1)

📍 step1

첫번째 열을 누적해서 더하기 수월하게 하기 위해서,
grid 를 첫 열의 원소들을 담을 리스트를 first_columns 에 담는다.

📍 step2

최소값을 구하는 함수 sum_path를 선언 한다.
sum_path 함수는 중첩 리스트에서
내부 리스트의 한 원소의 인덱스를 x,
외부 리스트의 인덱스를 y로 하여

(0,0)에서 (x,y)로 올 때 까지의
최소 경로를 재귀적인 방법으로 구하는 재귀 함수다.

📍 step3

외부 함수에서 sum_path(x, y)를 호출하고 반환 한다.

🎯 내 풀이

(다이나믹 프로그래밍)

import time

start = time.time()

def min_path_sum(grid):
#step1
    result = [[0] * len(grid[0]) for i in range(len(grid))]
    first_columns = [grid[i][0] for i in range(len(grid))]

#step2
    for i in range(len(result[0])):
        result[0][i] = sum(grid[0][:i+1])

    for i in range(len(first_columns)):
        result[i][0] = sum(first_columns[:i+1])

#step3
    for i in range(1, len(grid)):
        for j in range(1, len(grid[0])):
            result[i][j] = min(result[i-1][j], result[i][j-1]) + grid[i][j]

    print(result)
    print(grid)

    return result[len(grid) - 1][len(grid[0])-1]


print(min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))
print(min_path_sum([[1, 4, 5, 2], [3, 1, 2, 3]]))

end = time.time()

print(f"{end - start:.5f} sec")

📍 step1

경로의 최소값을 담을 리스트 result와
grid의 첫 열을 수월하게 더하기 위해,
first_columns에 grid 의 첫열의
원소만 원소로 담는다.

📍 step2

가장 바깥 쪽으로 이동하는 경우를 고려하기 위해
가장 바깥 쪽 행, 열 방향만으로 이동하며 누적하여 result에 담는다.

📍 step3

result에 (1,1), (1,2) ... (2,0),(2,1), ... (x, y-1), (x-1, y)까지의 최소값들을 담으며, 최종적으로 (x, y)의 값을 구하고, 반환한다.