[프로그래머스] 등굣길

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42898#

풀이

DP 를 활용한 풀이

주의할 점 1 : 주어진 웅덩이 좌표는 배열 좌표가 아닌 가로, 세로 좌표이다.
그래서 [3,1] 인 경우 dp[1][3] 이 된다.

일단 첫 번째 행과 열은 오른쪽, 아래 로만 이동할 수 있다는 조건으로 인해 갈 수 있는 경우의 수가 1이므로 1을 할당해준다.

다음은 웅덩이를 설정해줘야한다.
주의할 점은 첫번째 행 또는 열에 웅덩이가 있는 경우 그 다음 칸 부터는 갈 수 없게 되므로
그 이후의 칸들을 모두 0으로 처리해줘야한다.

이후 dp 점화식을 통해 답을 구해준다.

def solution(m, n, puddles):
    dp = [[1] * (m+1) for _ in range(n+1)]
   
    for col, row in puddles:
        dp[row][col] = 0
        if row == 1:
            for i in range(col, m+1):
                dp[row][i] = 0
        if col == 1:
            for i in range(row, n+1):
                dp[i][col] = 0
       
    for row in range(2, n+1):
        for col in range(2, m+1):
            if dp[row][col] == 0:
                continue
            dp[row][col] = (dp[row-1][col] + dp[row][col-1]) % 1_000_000_007
   
    return dp[-1][-1]