[프로그래머스] 등굣길

https://programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

다이나믹 프로그래밍을 이용하는 문제입니다.

 

우선 문제부터 요약해보면, 

m*n의 격자 판에서 등교를 하게 되고 물웅덩이가 있습니다. 이때, 물웅덩이를 밟지 않고, 오른쪽과 아래로만 이동하여 학교로 도착하는 최단 경로의 갯수를 return해야 합니다. 

 

즉 solution(m,n,puddles)에 

m,n : 격자의 크기

puddles : 물웅덩이의 위치

가 들어올 때, 최단 경로의 수를 return해야 합니다.

 

<Solution>

이 문제의 경우 최단 경로 찾기 문제와 똑같습니다. 특정칸으로 이동하는 경로의 최소 횟수를 구하고싶다면 그 경로의 바로 윗칸으로 이동하는 경우의 수와, 바로 왼쪽 칸으로 이동하는 경우의 수를 더해주면 됩니다.

 

주의해야하는 점은 

1. puddle을 밟는 경우를 고려해주어야한다. 2. outofblock도 고려해주어야한다. 3. 1,000,000,007로 나누는 것 4. puddle이 row,column이 아니라 column,row인점

이 부분들에만 주의하여 코드를 작성하면 됩니다.

 

실제 구현은 아래와 같습니다. 

def solution(m, n, puddles):
    def oob(row,column):
        return row>=n or row<0 or column>=m or column<0
    
    dp = [[0]*m for _ in range(n)]
    dp[0][0] = 1

    for j in range(m):
        for i in range(n):
            if i==0 and j==0:
                continue

            if (not oob(i,j-1)) and ([j-1+1,i+1] not in puddles):
                temp1 = dp[i][j-1]
            else:
                temp1 = 0
            if (not oob(i-1,j)) and ([j+1,i-1+1] not in puddles):
                temp2 = dp[i-1][j]
            else:
                temp2 = 0
            dp[i][j] = (temp1+temp2) % (int(1e9)+7)
            

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