Programmers - 등굣길

문제 링크

d[i][j] 가 (i,j)에 도착 할 수 있는 경우의 수 라고 할때
(i,j)에 도달하는 방법은 위(i-1,j)에서 오는 방법과 왼쪽(i,j-1) 에서 오는 방법이 있다.
d[i][j] = d[i-1][j] + d[i][j-1] 이다.

물에 잠긴 지역은 무시하고 위의 식을 적용하면 도착지에 도달하는 경우의 수를 구할 수 있다.

나는 보통 좌측 상단을 (0,0)으로 생각하고 1칸 아래를 (1,0), 1칸 오른쪽을 (0,1)로 생각한다.
그러나 문제에서 주어지는 입력은 내 생각과는 다르게 주어졌는데, 그 점만 주의 하면 문제를 푸는데 어려움은 없었다.

def solution(m, n, puddles):

    MOD = 1000000007
    d = [[0 for _ in range(m)] for _ in range(n)]
    puddles = set(map(lambda x: (x[1]-1, x[0]-1), puddles))

    d[0][0] = 1
    for i in range(n):
        for j in range(m):
            if (i, j) in puddles:
                continue

            if i >= 1:
                d[i][j] += d[i-1][j] % MOD
            if j >= 1:
                d[i][j] += d[i][j-1] % MOD
            d[i][j] %= MOD

    return d[n-1][m-1]