프로그래머스 : 등굣길

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

코딩테스트 연습 - 등굣길

고등학생 때 배운 확률과 통계 중 길찾기 문제를 구현하는 문제라고 볼 수 있다.

현재 칸의 윗 칸까지의 최단거리 + 현재 칸의 왼쪽 칸까지의 최단거리 = 현재 칸 까지의 최단거리

def solution(m, n, puddles):
    routes = []
    for i in range(n):
        routes.append([0]*m)
    for i in puddles:
        routes[i[1]-1][i[0]-1] = -1

    routes[0][0] = 1
    
    for y in range(n):
        for x in range(m):
            if routes[y][x] == -1:
                continue
                
            if y-1 >=0 and routes[y-1][x] != -1:
                routes[y][x] += routes[y-1][x]
            
            if x-1>=0 and routes[y][x-1] != -1:
                routes[y][x] += routes[y][x-1]
        
    answer = routes[n-1][m-1]
    return answer %1000000007