문제 설명

문제는 이 곳 링크를 참조하길 바란다.

• https://programmers.co.kr/learn/courses/30/lessons/42898

전체 코드

from collections import deque 

def solution(m, n, puddles):
    matrix = [[0]*(m+1) for _ in range(n+1)]
    matrix[1][1] = 1

    for i in range(1,n+1):
        for j in range(1,m+1):
            if i == 1 and j == 1:
                continue
            if [j,i] in puddles:
                matrix[i][j] = 0
            else:
                matrix[i][j] = matrix[i-1][j]+matrix[i][j-1] 

    return matrix[n][m] % 1000000007

해결 방법

동적배열법으로 왼쪽위 집에서 학교까지 모든 경우의 수를 계산하여 가는 문제이다. 따라서 matrix라는 m+1, n+1짜리 0 행렬을 만들고 i는 1부터 n+1, j는 1부터 m+1까지 메모이제이션 기법을 실행하는데 이때 문제에서 보면 표에서 그려지는 좌표가 반대로 구성되어 있음을 알 수 있다. 따라서 pudlles가 있는 것을 확인하기 위해 i,j의 위치를 바꾸어 확인을 한다.