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

 

나의 풀이

def solution(m, n, puddles):
    dp = [[0]*(m+1) for _ in range(n+1)]
    print(dp)
    for i in range(1, n+1) :
        for j in range(1, m+1) :
            if i == 1 and j == 1 : 
                dp[i][j] = 1
            elif [j,i] in puddles :
                dp[i][j] = 0
            else :
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            # print("dp[{}][{}] = {}".format(i,j,dp[i][j]))
    
    return dp[n][m] % 1000000007

• (1,1) 을 집으로, (n,m) 을 학교 좌표로 만들기 위해, 이차원 배열을 [n+1][m+1] 의 크기로 초기화한다.
• 이번 문제는 최소 경로의 길이를 구하는 것이 아니라, 최소 경로의 개수를 구하는 것이다.
• 문제에서는 항상 오른쪽 혹은 아래쪽으로만 이동한다고 하였는데, 이는 어떻게 가더라도 항상 최단 경로로 이동하는 것이다. 
• 따라서 현재 위치까지 올 수 있는 경우의 수를 구하면 된다.
• 즉, dp[x][y] = dp[x-1][y] + dp[x][y-1] 을 뜻한다.
• 현재 위치 까지 올 수 있는 경우의 수는, 현재 위치의 위쪽까지 오는 방법 + 현재 위치의 왼쪽까지 오는 방법과 같다.
• 만약, 물웅덩이 좌표에 도착한다면, 해당 좌표에는 도달할 수 없게 하기 위해 dp[x][y] = 0 으로 할당한다.

* puddles 안에 있는 물웅덩이의 좌표는 (y,x) 로 표기되어 있다.... 

처음에 다 맞게 푼 것 같은데 테스트케이스 1개 빼고 다 틀려서 당황함...ㅎㅎ

따라서 [j,i] in puddles 로 y,x 좌표를 바꿔주어야한다.

 

 

 

m=4, n=3 의 위 테스트케이스에 대한 dp[] 는 다음과 같다.