프로그래머스|등굣길

문제 설명

집에서 학교까지의 물웅덩이를 피하며 이동하려고 할 때 아래 또는 오른쪽으로만 이동하며 학교에 도착하는 최단 경로의 개수를 구하는 문제입니다.

작동 순서

1. 도로 상황을 입력받을 road 배열을 생성합니다.
2. 각 위치까지의 최단 거리를 저장할 DP 배열을 생성합니다. 그리고 첫 번째 칸에는 1을 지정해줍니다.
3. 오른쪽과 아래쪽으로만 이동할 수 있으면 어떤 식으로 이동하던지 무조건 돌아가는 길 없이 최단 거리이므로 해당 칸으로 이동할 수 있는 모든 경로의 개수를 구하면 됩니다. 모든 경로의 개수를 구하는 방법은 자신의 위쪽과 왼쪽에 도착하는 경로의 개수의 합입니다.
4. 경로를 모두 계산하였으면 DP 배열에서 학교가 있는 위치의 값을 출력해줍니다.

소스코드

def solution(m, n, puddles):
    road = [[0 for _ in range(m)] for _ in range(n)]
    dp = [[0 for _ in range(m)] for _ in range(n)]
    move=[[-1, 0], [0, -1]]
    
    for puddle in puddles:
        road[puddle[1]-1][puddle[0]-1]=1
    
    dp[0][0]=1
    
    for x in range(n):
        for y in range(m):
            if road[x][y]==0:
                for i in range(2):
                    prevX, prevY = x+move[i][0], y+move[i][1]
                    if n > prevX >= 0 and m > prevY >= 0:
                        dp[x][y]+=dp[prevX][prevY]%1000000007
                        dp[x][y]%=1000000007

    return dp[n-1][m-1]