문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42898

---

문제 파악

웅덩이를 피해서 (1,1) 에서 (m,n)으로 가는 최소거리의 개수를 구해야 한다.
그림은 면을 따라 이동해야 하는 것 처럼 보이지만, 평소 그래프 문제 풀듯이
점을 따라 이동해도 무방하다.

그래프가 주어지고, 최단거리 문제이기에 BFS로 풀 수 있을 것 같이 생겼지만, 최단거리를 구하는 문제가 아니라, 최단거리 경로의 개수를 구하는 문제이기에 DP로 풀어야 한다.

해결 아이디어 (DP)

DP 정의:

• dp[y][x] = (1,1)에서 (x,y)까지 오는 경우의 수
  점화식:
• 물웅덩이가 아니면:
  • dp[y][x] = dp[y-1][x] + dp[y][x-1] (위에서 오거나, 왼쪽에서 오거나)
• 물웅덩이면:
  • dp[y][x] = 0
    초기값:
• dp[1][1] = 1 (시작점)

최종답:

• dp[n][m] % MOD

해답 및 풀이

# m 가로, n 세로, puddles 맨위 
# 4, 3 , [[2,2]]
# puddle은 1개 이상, 10개 이하
def solution(m, n, puddles): 
    
    MOD = 1000000007
    
    # 방문 배열 (1-based index 사용)
    cnt = [[0 for _ in range(m+1)] for _ in range(n+1)]
    
    cnt[1][1] = 1 # 시작점

    # puddles = [[1,2],[2,3]]
    for x,y in puddles:
        cnt[y][x] = -1 # 웅덩이를 0으로 넣어줌
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            if cnt[i][j] == -1: # 웅덩이면,
                cnt[i][j] = 0 # 무조건 0으로 초기화
            elif not (i ==1 and j ==1): # 그렇지 않다면, 그리고 시작점이 아니라면,
                cnt[i][j] = (cnt[i-1][j] + cnt[i][j-1]) % MOD
            
    return cnt[n][m]

---

다음날 풀어본 코드

def solution(m, n, puddles):
    MOD = 1000000007
    
    # dp[i][j] = i,j 도달할때 까지 최단거리의 개수
    dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
    # [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]
    
    for x, y in puddles:
        dp[y][x] = -1
    # [
    # [0,0,0,0,0],
    # [0,0,0,0,0],
    # [0,0,-1,0,0],
    # [0,0,0,0,0]
    # ]       
    # 1-based index로 설정
    
    dp[1][1] = 1 # 시작점 세팅
    
    for i in range(1,n+1): # 세로
        for j in range(1,m+1): # 가로
            # 물웅덩이면
            if dp[i][j] == -1:
                dp[i][j] = 0 # 물웅덩이는 0으로 처리
            # 물웅덩이 아니고    
            else:
                # 시작점도 아니면
                if not (i==1 and j==1):
                    dp[i][j] = dp[i][j-1] + dp[i-1][j]
                
    return (dp[n][m] % MOD)