[Programmers] Lv.3 등굣길 (python)

문제 링크

link 📃 

문제 풀이

• 처음에 puddles의 좌표가 반대로 되어있는지 몰랐는데 이것 때문에 틀렸었다..! 🤣
• arr[i][j] = arr[i][j-1] + arr[i-1][j] 이 점화식을 사용해서 arr를 갱신해주었다.
• 해당 그림처럼 왼쪽과 위쪽의 값들을 더해 arr[i][j]를 만들어 주었다.

다른풀이 탐색

• if [i, j] in puddles를 사용해서 굳이 하나하나 체크하지 않아도 쉽게 풀 수 있는 방법이 있었다!

나의 해결 코드

Python

from collections import deque 
def solution(m, n, puddles):
    answer = 0
    arr = [[0 for _ in range(m+1)] for _ in range(n+1)]

    for p in puddles:
        x,y = p
        arr[y][x] = -1
    
    arr[1][1] = 1
    
    for i in range(1,n+1):
        for j in range(1,m+1):
            if arr[i][j] == -1:
                continue
            if arr[i-1][j] == -1 and arr[i][j-1] == -1:
                continue
            elif arr[i][j-1] == -1:
                arr[i][j] += arr[i-1][j]
            elif arr[i-1][j] == -1:
                arr[i][j] += arr[i][j-1]
            else:
                arr[i][j] += (arr[i][j-1] + arr[i-1][j])
        
    
    return arr[n][m] % 1000000007

print(solution(7, 4, [[2, 1], [2, 2], [2, 3], [4, 2], [4, 3], [4, 4], [6, 2], [6, 3]]))