[programmers/py] 등굣길

등굣길

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

문제 설명

• 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.
• 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.
• 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

문제 풀이

• dp를 통해 위쪽과 왼쪽에서 올 수 잇는 경로 수를 더한 값을 저장

def solution(m, n, puddles):
    arr = [[0]*(m+1) for i in range(n+1)]
    
    if puddles != [[]]:
        for a, b in puddles:
            arr[b][a] = -1 
            
    arr[1][1] = 1
    
    for i in range(1,n+1):
        for j in range(1,m+1):
            if i == j == 1:
                continue
            
            if arr[i][j] == -1:
                arr[i][j] = 0;
                continue
            
            arr[i][j] = arr[i-1][j] + arr[i][j-1]
            
    return arr[n][m]%1000000007