[프로그래머스] 등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898
문제를 어떻게 풀어야 하는지에 대한 생각을 하는 데에는 크게 어려움을 겪지 않았으나, 구현에 있어서 어려움을 겪은 문제이다.

웅덩이가 있는 곳을 제외하여, 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 경로의 경우의 수를 구하는 문제이다.
점화식은, 원하는 위치로의 경로의 수는 (윗 칸까지의 경로의 수)와 (왼쪽 칸까지의 경로의 수)의 합과 같다.

def solution(m, n, puddles):
    puddles = [[q,p] for [p,q] in puddles]      # 미리 puddles 좌표 거꾸로
    dp = [[0] * (m + 1) for i in range(n + 1)]  # dp 초기화
    dp[1][1] = 1           # 집의 위치(시작위치)

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if i == 1 and j == 1: continue 
            if [i, j] in puddles:    # 웅덩이 위치의 경우 값을 0으로
                dp[i][j] = 0
            else:                    # 현재 칸은 왼쪽 칸, 위 칸의 합산!
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007
    return dp[n][m]

풀이법도 간단하고, 아이디어를 떠올리기도 어렵지 않은 이 문제를 푸는 데 애를 먹었다.

나는 dp 테이블을 n*m사이즈로 만들어, 맨 왼쪽라인과 맨 오른쪽 라인은 경로 값을 모두 1로 초기화 해두고 시작헀다.

dp[i][j] = dp[i-1][j] + dp[i][j-1]

이 부분에서 문제가 발생했다.
나의 처음 풀이의 경우 for 문을 (1, n)과 (1, m)에서 돌리게 되면 맨 위쪽과 맨 왼쪽 테두리 라인에 웅덩이가 생기는 부분을 체크하지 못해 케이스가 복잡해진다.
이러한 부분을 해결하기 위해 for문을 0부터 돌리게 되면 i-1과 j-1이 음수가 되는 곳에서 문제가 발생한다.
배열의 인덱스가 음수가 되면 배열의 맨끝값을 가져와 사용하기 때문이다.

핵심

이처럼 배열의 인덱스가 음수가 될 경우까지 일반화 하고자 한다면 테이블을 1+n, 1+m의 크기로 만들어 (1,1)부터 사용하고, i-1이나 j-1이 0이 되는 경우에도 문제가 발생하지 않도록 적절한 조치를 취해주어야 한다.