문제 조건

input

• 정수 m,n
• 정수 배열 puddles
• 1 ≤ m,n ≤ 100
• 1 ≤ puddles ≤ 10

output

• 최단 경로의 개수

문제 해석

• 경로는 (0,0)에서 시작해서 우, 아래 방향만 이동 가능
• 시간 복잡도는 여유있음
• dp 배열 생성해서 값 누적
  • dp[i][j]: i,j에 올 수 있는 경로의 수
• 조건
  1. 웅덩이
  2. 좌표 경계 조건

코드

def solution(m, n, puddles):
		# 좌표 초기화
		# [0 * 행의 개수(n)] * 열의 개수(m)
    dp = [[0] * n for _ in range(m)]

    # 시작점 1로 초기화
    dp[0][0] = 1
    
    # 웅덩이 탐색의 효율을 고려해, set 생성
    puddle_set = set()
    
    for (i, j) in puddles:
        puddle_set.add((i, j))
    
    # m * n만큼 반복
    for i in range(m):
        for j in range(n):
            
            # 웅덩이    
            if (i+1, j+1) in puddle_set:
                continue
            
            # 경계 조건 1: (0,0)
            if i < 1 and j < 1:
                continue
                
            # 경계 조건 2: 1열일 경우, 오른쪽에서 오는 이전 경로 사용 불가  
            elif i < 1: 
                dp[i][j] = dp[i][j-1]
            
            # 경계 조건 3: 1행일 경우, 아래에서 오는 이전 경로 사용 불가
            elif j < 1:
                dp[i][j] = dp[i-1][j]
            
            # 모든 조건에 해당하지 않은 경우, 모든 경로 사용 가능
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

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