[level 3] 등굣길

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

프로그래머스

핵심포인트

✅ 행과열이 m,n이 아니라 n,m이라는 것에 유의하면 쉬운 문제!

✅ index를 0에서부터가 아니라 행 기준 [1,n], 열 기준 [1,m] 범위로 설정하면 더 간단함

#dynamic programming

def solution(m, n, puddles):
    memo=[[0 for i in range(m+1)] for j in range(n+1)]
    memo[1][1]=1
    for i in range(n+1):
        for j in range(m+1):
            if i==1 and j==1:
                continue
            if [j,i] in puddles:
                continue
            memo[i][j]=memo[i-1][j]+memo[i][j-1]
            
    return memo[-1][-1]%1000000007

#dfs

def solution(m, n, puddles):
    map = [[0 for _ in range(m)] for _ in range(n)]
    for x, y in puddles:
        map[y-1][x-1] = -1
    map[0][0] = 1
    return dfs(m-1, n-1, map)

def dfs(x, y, map):
    if x < 0 or y < 0 or map[y][x] == -1:
        return 0
        
    if map[y][x] == 0:
        map[y][x] = dfs(x-1, y, map) + dfs(x, y-1, map)

    return map[y][x] % 1000000007