[프로그래머스] 등굣길(python 파이썬)

최단경로의 개수를 구하는 문제이다..

문제를 잘못읽어서 최단경로를 구하는 문제인줄 알았다....(몇시간을 날린건지..)

 

오른쪽과 아래로만 이동할 수 있다.

중학교때 배운 경로의 수 구하는 문제를 알면 풀 수 있는 문제이다.

 

1, x 좌표를 1로 채운다 (-1이 하나라도 있으면 그 이후에는 -1로 채운다.)

x, 1 좌표를 1로 채운다 (-1이 하나라도 있으면 그 이후에는 -1로 채운다.)

 

해당 좌표로 올 수 있는 경우의 수는 해당좌표의 위, 왼쪽을 더한 값이다. (-1이 있다면 -1이 아닌 값을 넣어준다.)

m, n의 좌표가 답이다.

하지만

이렇게 풀면 학교에 도착하지 못하는 경우에는 m, n 좌표에 -1이 들어간다.

예외처리를 하여 -1일경우 0을 반환해준다.

 

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

    for puddle in puddles:
        if puddle:
            dp[puddle[0]][puddle[1]] = -1

    m_one_check = False
    for i in range(n + 1):
        if dp[1][i] == -1:
            m_one_check = True
        if m_one_check:
            dp[1][i] = -1
        else:
            dp[1][i] = 1

    m_one_check = False
    for i in range(1, m + 1):
        if dp[i][1] == -1:
            m_one_check = True
        if m_one_check:
            dp[i][1] = -1
        else:
            dp[i][1] = 1

    for i in range(2, m + 1):
        for j in range(2, n + 1):
            if dp[i][j] == -1:
                continue
            else:
                if dp[i - 1][j] == -1:
                    dp[i][j] = dp[i][j - 1]
                elif dp[i][j - 1] == -1:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    if dp[m][n] < 0:
        return 0
    return dp[m][n] % 1000000007