1. 문제 설명

등굣길

2. 문제 분석

각 위치로 이동 가능한 경우의 수의 총합은 (가능하다면) 왼쪽에서 오는 경우의 수 + 위쪽에서 오는 경우의 수의 총합이다. 마지막으로 도착지의 경우의 수를 return한다.

1. 주어진 행열 리스트를 만들고 시작점에 1, 웅덩이에 -1을 줘서 표시한다.
2. dp를 통해 왼쪽, 위쪽에 연결된 좌표의 경우의 수를 이용해 현재 좌표로 올 수 있는 경우의 수를 구한다.
3. 가장 왼쪽, 가장 위쪽인 좌표를 따로 구분한다. 연결된 좌표에 웅덩이가 있는 경우는 0으로 카운트한다.

3. 나의 풀이

def solution(m, n, puddles):
    dp = [[0 for _ in range(m)] for _ in range(n)]
    dp[0][0] = 1
    # 시작점

    for row, col in puddles:
        dp[col-1][row-1] = -1
        # 웅덩이 표시

    for row in range(n):
        for col in range(m):
            if dp[row][col] == -1: continue
            # 웅덩이면 피해가자
            if row == 0 and col == 0: continue
            # 시작점이므로 패스
            
            if row == 0:
                if dp[row][col-1] == -1: continue
                dp[row][col] = dp[row][col-1]
                # 맨 위 층에서는 왼쪽에서 오는 경우만 카운트. 웅덩이가 있을 때에는 그대로 0.
            if col == 0:
                if dp[row-1][col] == -1: continue
                dp[row][col] = dp[row-1][col]
                # 맨 왼쪽 층에서는 위에서 오는 경우만 카운트. 웅덩이가 있을 때에는 그대로 0.
            
            dp[row][col] = dp[row-1][col] + dp[row][col-1]
            # 최단 경로는 왼쪽과 위쪽에서 오는 경우의 수의 총합
            if dp[row-1][col] == -1: dp[row][col] += 1
            if dp[row][col-1] == -1: dp[row][col] += 1
            # 웅덩이가 있는 경우를 더한 경우는 다시 원상복귀.

    return dp[n-1][m-1]%1000000007