문제

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

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

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

Output: 7

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

나의 풀이

이건 BFS(Breadth First Search)공부를 해보신 분이면 쉽게 풀수 있을 문제인듯 하다.

1. queue를 이용하여 첫번째 위치에서 갈수 있는 모든 좌표, 그리고 두번째 위치에서 갈수 있는 모든 좌표... n번째 위치에서 갈수 있는 모든 좌표들을 푸쉬한다.
2. 지나온 모든 좌표들에서의 합을 구한다.
3. 종착지에서 경로를 지나오면서 구한 합을 비교하여 가장 작은 값을 선택한다.

메인 로직은 위와 같다.

• 문제에서 오른쪽과 아래쪽만을 갈수 있다고 했으니, 오른쪽을 가기 위해서는 (x, y) 좌표에서 y의 값을 1 더해주면 되고, 아래쪽으로 가기 위해서는 x의 값에서 1을 더해주면 된다.
  오른쪽, 아래쪽을 편하게 사용하기 위해 direct변수에 오르쪽 좌표, 아래쪽 좌표를 미리 정의해 준다.
• 최초 시작점의 좌표인 (0, 0)과 (0, 0)의 좌표값을 리스트에 담아서 queue의 하나의 요소로써 사용할 수 있도록 한다.
  시작점과 시작점의 값을 담은 리스트를 임의로 지정한 q에 첫번째 값으로 넣어 준다.
• 첫번째 q에 담긴 요소를 temp 변수에 담아 for문으로 오른쪽, 아래쪽의 좌표를 dx, dy변수에 담아주고 만약에 dx, dy 변수 중, 입력받은 배열의 크기 이상인게 있다면 배열의 범위를 벗어난 것으로 간주한다.
• for문을 돌려 이동 가능한 좌표의 값 dx와 dy를 리스트의 첫번째, 두번째 요소로 넣고, 기존 좌표의 값과 dx, dy 좌표의 값을 더해서 리스트의 세번째 요소로 담는다.
  리스트에 담은 후, q의 하나의 요소로써 append한다.
• 위 과정을 q가 빌때 까지, 반복을 하면 처음부터 끝까지 이동된 모든 좌표를 계산하게 되므로 최종 목적지에서 값을 비교하여 가장 작은 값을 min에 담아서 return 한다.

def min_path_sum(grid):
  m = len(grid)
  n = len(grid[0])

  node = [0, 0, grid[0][0]]
  q = [node]
  direct = [
    [0, 1],
    [1, 0]
  ]

  min = 999999

  while(True):
    if not q: break

    temp = q.pop(0)

    for i in range(2):
      dx = temp[0] + direct[i][0]
      dy = temp[1] + direct[i][1]

      if dx >= m or dy >= n: continue
      if (dx == m - 1 and dy == n - 1) and min > temp[2] + grid[dx][dy]:
        min = temp[2] + grid[dx][dy]

      sum = temp[2] + grid[dx][dy]
      q.append([dx, dy, sum])

  return min