프로그래머스 알고리즘 - 등굣길

문제 접근

(1,1) 좌표부터 (m,n) 좌표까지 가는 최소 루트 개수 구하기.

해답 및 풀이

DP 테이블을 만들어서 dp[i][j] = (i,j)에 도달할 수 있는 경로의 수로 정의

초기값: dp[1][1] = 1 (시작점)

점화식:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
단, 해당 좌표가 물에 잠긴 곳이면 dp[i][j] = 0

def solution(m, n, puddles):
    MOD = 1_000_000_007

    # dp 테이블 초기화 (1-based index 사용)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    dp[1][1] = 1  # 시작점

    # 물에 잠긴 곳 표시
    for x, y in puddles:
        dp[y][x] = -1  # x: 열, y: 행

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if dp[i][j] == -1:
                dp[i][j] = 0  # 지나갈 수 없는 곳
            elif not (i == 1 and j == 1):  # 시작점은 제외
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD

    return dp[n][m]