Python - [프로그래머스]42898-등굣길

출처

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

문제

물 웅덩이를 피해 학교에 도달할 수 있는 최단경로의 갯수를 구하는 문제이다

풀이

보통의 최단경로를 구하는 방법은 오른쪽, 아래쪽으로 이동하는 경로를 고려하여 구한다. 그러므로 위쪽, 왼쪽에 있는 값을 누적시켜 더해주면 된다.
점화식으로 표현하면 dp[i][j] = dp[i-1][j] + dp[i][j-1]이 될것이다.

다만 여기서 추가적으로 고려해줄 부분은 물 웅덩이를 피해야 하기때문에 물 웅덩이 부분은 값을 더해주지 않고 0으로 계산하도록 한다.
그리고 또 하나 고려할 부분은 웅덩이 좌표를 반대로 준다,,,
웅덩이 좌표가 1, 3으로 주어지면 dp상에서는 3, 1이 맞는 인덱스이다.
이 부분만 고려하여 점화식 대로 구현해주면 된다.

코드

def solution(m, n, puddles):
    answer = 0
    dp = [[0]*m for _ in range(n)]
    def is_range(x, y):
        return 0<=x<n and 0<=y<m and dp[x][y]>=0
    for i in puddles:
        dp[i[1]-1][i[0]-1] = -1
    dp[0][0] = 1
    for i in range(n):
        for j in range(m):
            dx, dy = i-1, j-1
            if i == 0 and j == 0 or dp[i][j] == -1:
                continue
            else:
                if is_range(dx, j):
                    dp[i][j] += dp[dx][j]
                if is_range(i, dy):
                    dp[i][j] += dp[i][dy]
    answer = dp[-1][-1] % 1000000007
    return answer