프로그래머스 등굣길 파이썬

프로그래머스 파이썬 등굣길 프로그래머스 등굣길 파이썬 파이썬 프로그래머스 등굣길 파이썬 등굣길 프로그래머스 등굣길 프로그래머스 파이썬 등굣길 파이썬 프로그래머스

등굣길

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

문제 단순화

• 이차원 좌표 m,n 정수가 있다.
• 오른쪽과 아래쪽으로만 움직여 (1,1) 부터 (m,n)까지 이동할 수 있다.
• 물에 잠긴 지점의 좌표는 이동할 수 없다.
• 최단경로의 개수를 1000000007로 나눈 나머지를 리턴한다.

문제풀이

• 이차원 dp를 만든다.
• 되돌아 가는 경로를 포함하지 않기 때문에 도달하는 모든 경로가 최소 경로이다

팁

• 나머지 연산에 주의한다.

코드

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