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

Programmers 등굣길

코드

def solution(m, n, puddles):
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    puddles = [[q,p] for [p,q] in puddles]
    
    dp[1][1] = 1
    for i in range(1, n+1):
        for j in range(1, m+1):
            if i == 1 and j == 1:
                continue
            if [i, j] in puddles:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
          
    return dp[n][m] % 1000000007

풀이 과정

‘갈 수 있는 경로의 수’를 이전 위치들의 경로 수로 누적해서 구하는 문제이므로 DP를 활용하였다.

한 칸씩 이동하며 여기까지 오는 방법이 몇 가지인지를 저장해두는 방식이라고 보면 됐다.

동적 계획법 (Dynamic Programming)

동적 계획법은 큰 문제를 작은 문제로 나누고, 이미 구한 작은 문제의 결과를 저장해서 다시 사용하는 방식이다.

이 문제에서는 dp[i][j]를 (i, j) 위치까지 올 수 있는 경로의 수로 정의하였다.

→ 특정 위치까지 도달하는 경로의 수가 이전 위치들의 결과에 의존하기 때문에 각 칸의 답을 이전 칸의 답으로부터 구할 수 있기 때문에 DP를 사용해야겠다고 생각했다.

웅덩이 같은 경우에는 지나갈 수 없으므로 해당 위치의 경로 수를 0으로 설정했다.

웅덩이 칸의 경로 수가 0이 되면, 이후 칸을 계산할 때 자연스럽게 해당 경로는 제외된다.

첫 번째 열과 첫 번째 행 또한 위에서 온 경로와 왼쪽에서 온 경로가 더해져야하기 때문에 m+1, n+1 크기의 배열로 dp를 만들고 0으로 초기화하고, (1, 1)을 시작점으로 계산을 시작하였다.