[Programmers][동적계획법(Dynamic Programming)] 등굣길

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

최단 거리 문제이다.
처음에 공식으로 날먹할려다 '최단거리 - 방해물을 거쳐가는 길'은 방해물들을 거쳐가는 길에 중복이 생긴다는 것을 늦게 깨닫고 문제의 의도대로 동적 계획법을 사용해야됨을 절실히 깨달았다.

풀이 1

def solution(m, n, puddles):
    path = [[0]*m for i in range(n)]
    x = 0
    y = 0

    while [x+1, 1] not in puddles and x in range(m):
        path[0][x] = 1
        x += 1

    while [1, y+1] not in puddles and y in range(n):
        path[y][0] = 1
        y += 1

    for y in range(1,n):
        for x in range(1,m):
            if [x+1, y+1] not in puddles:
                path[y][x] = path[y-1][x] + path[y][x-1]


    return path[n-1][m-1]%1000000007

풀이 2

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

    for y in range(1, n+1):
        for x in range(1, m+1):
            if map[y][x] == -1:
                map[y][x] = 0
                continue
            map[y][x] += (map[y][x-1]+map[y-1][x])%1000000007

    return map[n][m]