문제 :
양수로 이루어진 m x n 그리드를 인자로 드립니다.
상단 왼쪽에서 시작하여, 하단 오른쪽까지 가는 길의 요소를 다 더했을 때,가장 작은 합을 찾아서 return 해주세요.
한 지점에서 우측이나 아래로만 이동할 수 있습니다.
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
설명: 1→3→1→1→1 의 합이 제일 작음

문제 접근 ⚙️

• 일단, 왼쪽 맨 상단에서 오른쪽 맨 아래로 접근하기 때문에 (0,0) 포지션에서 (len(list1)[0]-1,len(list1)-1) 와야된다.
• 오른쪽, 아래로만 움직인다.
• 다음 칸으로 움직일때, 현재의 값과 이전의 값이 더해진다.
• 뒤로 되돌아갈 수 없다.
• 목표 지점으로 올때까지의 점수의 합 중 가장 작은 값을 반환한다.

문제 푸는 방식 🤔

• 모든 경우의 수를 생각하여 목표지점에서 점수의 합산을 생각해야된다.
• 매 칸마다 2가지 경우의 수가 있고, 다음 칸으로 갈때 전 칸의 값을 저장해야된다.
• 여기서 아 ! 재귀식으로 풀면 되겠구나 감이왔다.
• 재귀함수란 ?

  재귀(recursion)은 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. -wiki 링크

• 위의 그림과 같이 계속 오른쪽으로 +1일때와 아래로 +1 일때를 따로 계속 호출해서 결국 목표 지점에 도달한 녀석들만 비교해서 제일 작은 수를 구하면 되겟구만 !

문제 해결

list1 = []

def min_path_sum(grid):

  def next(x,y,sum):
	# 범위 밖으로 안나가게 범위 조절하기 !
    if (x == (len(grid[0])-1)) and (y == (len(grid)-1)): 
      sum += grid[x][y]
      list1.append(sum)
    elif not ((x >= len(grid[0])) or (y >= len(grid))):
      sum += grid[x][y]
      next(x+1,y,sum)
      next(x,y+1,sum)
      

  next(0,0,0) #맨 처음 포인트부터 출발

  print(list1)
  return min(list1) # 제일 작은 애 뽑아오기

• 그냥 알고만 있던 재귀함수를 이렇게 알고리즘 문제에 적용하니 재밌네요 ㅎㅎ

끝 🌈