[프로그래머스] 등굣길 / 동적 계획법(Dynamic-Programming)

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

💭 문제 이해

 

격자를 오른쪽과 아래쪽으로 이동하며 최단 경로의 수를 측정하는 문제이다.

DP로 풀 수 있고, 물이 있는 부분을 어떻게 체크하느냐가 포인트인 문제이다.

 

 

 

구현 언어: Python

 

def solution(m, n, puddles):
    maps = [[0]*(m+1) for _ in range(n+1)]
    dp = [[0]*(m+1) for _ in range(n+1)]
    # 물 체크
    for pud in puddles:
        maps[pud[1]][pud[0]] = -1
        
    dp[1][0] = 1  # 시작지점은 1
    for i in range(1, n+1):
        for j in range(1, m+1):
            if maps[i][j] == -1:
                dp[i][j] = 0
            else:
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007
    return dp[n][m]

 

maps는 현재 지도의 상태를 나타내는 배열로서, 물이 있는 위치라면 그 곳을 -1로 기록해둔다.

dp는 이동 경로를 기록하는 배열로서, 물이 있는 위치라면 그 곳은 0이 된다. (이동할 수 없다는 뜻)

 

0	0	0	0	0
0	1
0		0
0

 

예제에 주어진 경로의 상태이다.

0행과 0열은 이동할 수 없는 공간으로서 0으로 채워지게 되고, 물로 채워진 공간 또한 0이 된다.

 

 

0	0	0	0	0
0	1	1	1	1
0	1	0	1	2
0	1	1	2	4

 

(1, 1) 위치부터 주어진 귀납식에 따라 채워나가면 최종 목적지인 (n, m)에 최단경로의 수를 찾을 수 있게 된다.