[ Lv 3 ] 등굣길

풀이과정

---

1. 오른쪽과 아래로만 이동 가능하므로 점화식을 세우면..

   dp[i][j] = dp[i-1][j] + dp[i][j-1] 이다.

2. 단, 여기서 웅덩이가 있을 수도 있으므로 웅덩이는 따로 INT_MAX값을 넣어주어서 만약 현재 자기 위치 기준 왼쪽이나 위가 웅덩이라면 계산하지 않도록 처리해 준다.

3. 첫째 열/행은 일직선으로 가는 경우가 최단거리이므로 1로 처리하지만, 이때도 웅덩이를 만나게 된다면 break해주어야 한다.

4. 문제 자체가 일반적인 행,열 순서가 아닌 열,행 순서로 주어지기 때문에 헷갈림.

---

from collections import deque

def solution(m, n, puddles):
    answer = 0
    INT_MAX = int(10e9)
    dp = [[0] * m for _ in range(n)]

    for a,b in puddles:
        dp[b-1][a-1] = INT_MAX
    # initiate
    for i in range(m):
        if dp[0][i] == INT_MAX:
            break
        dp[0][i] = 1

    for i in range(n):
        if dp[i][0] == INT_MAX:
            break
        dp[i][0] = 1

    for i in range(1, n):
        for j in range(1, m):
            temp = 0
            if dp[i][j] == INT_MAX:
                continue
            if dp[i-1][j] != INT_MAX:
                temp += dp[i-1][j]
            if dp[i][j-1] != INT_MAX:
                temp += dp[i][j-1]
            dp[i][j] = temp


    answer = dp[n-1][m-1] % 1000000007

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges