프로그래머스 Level3 "등굣길"

문제

프로그래머스 Level3 '등굣길'

풀이

최소 동선으로 움직이기 위해선 왼쪽에서 오른쪽 혹은 위에서 아래 두가지 방향으로 움직이게 되니, 해당 위치로 가는 최소 동선은 해당 위치의 위쪽과 왼쪽으로 가는 최소동선의 합이 된다.
즉, 반복문을 돌리면서 dp[i][j] = dp[i-1][j] + dp[i][j-1]로 처리하면 된다.

만약 dp[j][i]가 웅덩이인경우 0으로 처리하고 지나간다.

Python 코드

def solution(m, n, puddles):
  dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
  dp[1][1] = 1
  for i in range(1, n+1):
    for j in range(1, m+1):
      if dp[i][j] == 1:
        continue
      elif [j, i] in puddles:
        dp[i][j] = 0
      else:
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
  return dp[n][m]%1000000007