CodeKata - grid (메모화)

문제

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

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

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

Output: 7

설명: 1→3→1→1→1 의 합이 제일 작음

내 코드

memo = {}
def minPathSum(grid):
  def loof(x,y,gird):
    point = '{},{}'.format(x, y)
    if point == '0,0':
      memo[point] = grid[0][0]
      return grid[0][0]
    elif point in memo.keys():
      return memo[point]
    else:
      if x == 0:
        point_sum = memo['{},{}'.format(x, y-1)]+grid[x][y]
        memo[point] = point_sum
        return memo[point]
      elif y == 0:
        point_sum = memo['{},{}'.format(x-1, y)]+grid[x][y]
        memo[point] = point_sum
        return memo[point]
      else:
        point_sum = min(memo['{},{}'.format(x, y-1)]+grid[x][y], memo['{},{}'.format(x-1, y)]+grid[x][y])
        memo[point] = point_sum
        return memo[point]
  
  for x in range(len(grid)):
    for y in range(len(grid[0])):
      result = loof(x,y,grid)
  return result

설명
1) 재귀함수와 메모화를 사용하기 위해 함수 안에 또 함수를 만듦
2) 조건을 3가지 경우로 생각함

• x 축으로만 이동하는 경우
• y 축으로만 이동하는 경우
• x, y 모두 이동하는 경우

3) x, y축으로 모두 이동하는 경우 해당 포인트로 이동하는 경로가 2개가 되고 그 중 경로의 합이 최소가 되는 경우만 저장

모법답안

def minPathSum(grid):
    m = len(grid)
    n = len(grid[0])
    
    for i in range(1, n):
        grid[0][i] += grid[0][i-1]
        
    for i in range(1, m):
        grid[i][0] += grid[i-1][0]
        
    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i-1][j], grid[i][j-1])
            
    return grid[-1][-1]

설명
1) 따로 경로의 합을 저장하지 않고 입력 받은 grid 배열에 해당 포이트까지의 합을 저장함
2) 조건에 따라 한 칸씩 저장하는 것이 아니라 x축에 관한 경로를 일괄적으로, y축에 관한 경로도 일괄적으로 계산 후 x, y축이 동시에 움직이는 경로에 대해서 계산
3) x, y축이 모두 움직이는 경로는 2가지가 나오므로 그 중 최솟값이 되는 경로만 선택

평가

내 코드와 모범답안이 문제를 풀어가는 개념이나 방향은 어느 정도 일치한다고 생각한다. 그러나 내 코드는 굳이 메모화나 재귀함수를 안 써도 되는데 사용한 느낌이 들었고, 조건을 안 나누고 할 수 있다는 것을 모범답을 통해 배웠다.
그래도 재귀함수 + 메모화을 생각한 대로 구현 했다는 점은 만족한다.