[프로그래머스] 등굣길 (Dynamic Programming, python, 파이썬)

웅덩이를 피해 학교로 가는 모든 경로의 수를 구하는 문제이다. 방향은 오른쪽과 아래쪽으로만 갈 수 있다.

모든 경로의 수를 1,000,000,007로 나눈 나머지를 return한다.

def solution(m, n, puddles):
    mod=10**9+7
    dp=[[0]*(m+1) for _ in range(n+1)]
    puddles_set=set((y,x) for x,y in puddles)
    dp[1][1]=1
    for i in range(1,n+1):
        for j in range(1,m+1):
            if (i,j) in puddles_set:
                dp[i][j]=0
            else:
                if i>1 :
                    dp[i][j]+=dp[i-1][j]%mod
                if j>1 :
                    dp[i][j]+=dp[i][j-1]%mod
                dp[i][j]%=mod
 
    return(dp[n][m])

주의할 점은 (m,n)이 (4,3)일 경우 3행 4열을 의미한다. row=3 col=4인 것이다.

• (1,1)에서 출발하기 때문에 (n+1)*(m+1)의 2차원 리스트 dp를 만들어 준다.
• 좌표를 반대로 보는 것이 직관적이기에 puddles또한 x좌표와 y좌표를 교차하여 puddles_set에 재할당한다.
• dp[1][1]을 은 출발점 이므로 1을 할당한다.
• 이중반복문을 활용하여 경로의 수를 구한다.
  • (i,j)가  puddles_set에 있다면 dp[i][j]는 0을 할당한다.
  • 나머지 좌표는 구간합을 이용하여 dp[i][j]에 경로의 수를 할당한다.
• 1,000,000,007로 나눈 나머지를 return해야 하므로 mod에 1,000,000,007을 할당하고 dp에 값이 할당 될 때마다 나머지 계산을 하여 dp의 값이 커지는 것을 방지한다. 1,000,000,007은 매우 큰 소수이기 때문에 나머지 연산용으로 많이 사용됩니다.