[Python][DP] 등굣길 - 프로그래머스

[문제]

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

프로그래머스

[알고리즘]

• DP 문제이다. 
• 오른쪽, 아래로만 움직일 수 있으니 현재 위치(i, j)까지의 최단 경로 개수는 위(i-1, j)와 왼쪽(i, j-1)의 최단 경로 개수의 합이다. 
• 단, puddle이 존재할 경우는 이를 지나쳐 오른쪽이나 아래로 갈 수 없으니, puddle 위치의 최단 경로는 0으로 설정한다.

[느낀점]

•  1,000,000,007로 나눈 나머지를 return 한다는 것을 잊지 말기

[코드] - 31분 소요

def solution(m, n, puddles):
    answer = 0
    ans_2d = [[0 for _ in range(m)] for _ in range(n)]
    
    for j, i in puddles:
        ans_2d[i-1][j-1] = -1
    
    is_puddle = False
    for i in range(n):
        if ans_2d[i][0] == -1 : 
            is_puddle = True
        if is_puddle : 
            ans_2d[i][0] = 0
        else : 
            ans_2d[i][0] = 1
    
    is_puddle = False 
    for j in range(m):
        if ans_2d[0][j] == -1 :
            is_puddle = True
        if is_puddle :
            ans_2d[0][j] = 0
        else : 
            ans_2d[0][j] = 1
    
    for i in range(1, n):
        for j in range(1, m):
            if ans_2d[i][j] == -1 :
                ans_2d[i][j] = 0
                continue
            ans_2d[i][j] = (ans_2d[i-1][j] + ans_2d[i][j-1]) % 1000000007
                
    
    return ans_2d[n-1][m-1]

 

간단한 코드 참고 : https://dev-note-97.tistory.com/141