[프로그래머스] Lv3. 등굣길

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42898#qna

프로그래머스

코드

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

풀이

• 집의 위치를 1로 시작하고, 웅덩이가 있는 좌표는 -1로 표시한다.
• 이중 for문을 돌다 웅덩이를 만나면 웅덩이 값은 0으로 만든다.
• 오른쪽, 아래쪽으로만 이동할 수 있으므로, 현재 좌표 기준 위, 왼쪽의 값을 더해서 1000000007로 나눈 나머지의 값으로 갱신해준다.