프로그래머스 - 등굣길

등굣길

설명

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

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

def solution(m, n, puddles):
    answer = 0
    table = [[0]*(m) for _ in range(n)]
    table[0][0] = 1
    for pos in puddles:
        y,x = pos
        table[x-1][y-1] = -1
    for x in range(n):
        for y in range(m):
            if table[x][y] != -1:
                # top = table[x][y-1]
                # left = table[x-1][y]
                if x>0 and table[x-1][y] != -1:
                    table[x][y] += table[x-1][y]
                if y>0 and table[x][y-1] != -1:
                    table[x][y] += table[x][y-1]
        # print(table)
    answer = table[n-1][m-1]%1000000007
    return answer

• 뭔가뭔가 BFS와 그래프에서 나올법한 문제
• 최단경로 -> 오른쪽하고 아래로만 움직이면 전부 최단경로가 됨, 신경쓰지 않아도 된다
• 그러면 계속 움직여가면서 위에서 오는 가짓수, 왼쪽에서 오는 가짓수 계속 더해가면 되지 않나?
• 위의 두 가지 조건을 한번에 작성하려니까 너무 복잡해지더라
• 위쪽 방향 더하고 왼쪽 방향 더하고 반복하다보면 끝