[프로그래머스] 등굣길

문제

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른족과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단 경로의 개수를 1,000,000,0007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지연은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

코드

INF = 1000000007
def solution(m, n, puddles):
    maps = [[[INF + 1, 0] for _ in range(m)] for _ in range(n)]
    
    for i in range(m):
        if [i+1,1] not in puddles:
            maps[0][i] = [i, 1]
        else:
            break
    for i in range(n):
        if [1,i+1] not in puddles:
            maps[i][0] = [i, 1]
        else:
            break
    for x in range(1,n):
        for y in range(1,m):
            if [y+1,x+1] not in puddles:
                up = maps[x-1][y]
                next = maps[x][y-1]
                if up[0] == next[0]:
                    maps[x][y] = [up[0]+1, up[1]+next[1]]
                elif up[0] > next[0]:
                    maps[x][y] = [next[0]+1, next[1]]
                else:
                    maps[x][y] = [up[0]+1, up[1]]
    
    return maps[n-1][m-1][1] % INF