[프로그래머스 level3 등굣길] dp 뿌시기!

해결해야하는 문제는 다음과 같았다.

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

코딩테스트 연습 - 등굣길

 

 

 

이 문제는 ,, 딱 보자마자 고등학교 때 배웠던 최단 경로 찾기 방법을 활용하려 하였는데,, 그냥 이 방법을 적용하면 약간의 오류가 난다.

그 이유는 아래와 오른쪽으로만 간다는 점에 유의해야하였기 때문이다!

 

처음에는 다음과 같은 아이디어로 접근하고자 하였다.

우선 puddle의 배열은 [col,row] 의 형태로 주어지고, 제시한 지도도 [col,row] 형태이지만 나는 [row,col] 형태가 편하기 때문에 dp_table은 nxm 의 형태로 지정하고 위와 같이 문제에 접근하였다.

 

하지만 이는 아래와 오른쪽으로만 간다는 조건을 어긴 경우이다.

 

따라서 이를 해결하기 위해 다음과 같은 생각을 하였다.

dp_table을 처음에 시작하는 위치는 갈 수 있다는 표시로 1을 하고, 갈 수 있는 길은 0으로, 갈 수 없는 길의 경우 -1로 초기화를 한다.

이렇게 생각하게 된 이유는 웅덩이가 없어 갈 수 있는 길이더라도 아래 방향, 오른쪽 방향으로만 가는 경우에는 현재 위치에 도달할 수 없을수도 있기 때문에 갈 수 있는 길을 0, 아예 갈 수 없는 길은 -1로 초기화하도록 하였다.

그리고 첫번째 위치인 문제에서의 [1,1] -> [0,0] 은 1로 표시하여 현재 도달하였다는 의미로 1로 정의하였다.

 

이후 첫번쨰 칸에서부터 갈 수 있는 칸에 대해 하나씩 처리하고자 하였다.

 

dp_table이 -1이 아니라면 갈 수 있는 경우이다. 따라서 갈 수 있는 경우 , 왼쪽/위쪽/ 왼쪽+위쪽/ 현재값을 비교하여 가장 큰 값을 저장하도록하였다. 첫번째 행 혹은 첫번째 열인 경우에는 앞줄에서 제시한 모든 방향을 갈 수 없으므로, 경우에 따라 다르게 처리하도록 하였다.

 

이러한 아이디어를 바탕으로 작성한 코드는 다음과 같다.

def solution(m, n, puddles):
    dp_table = [[0]*m for _ in range(n)]
    dp_table[0][0] = 1
    
    for col,row in puddles :
        dp_table[row-1][col-1] = -1
 
    for row in range(n):
        for col in range(m):
            if dp_table[row][col] != -1:
                if row == 0 and col == 0:
                    pass
                elif row == 0 :
                    dp_table[row][col] = max(dp_table[row][col], dp_table[row][col-1])
                elif col == 0:
                    dp_table[row][col] = max(dp_table[row][col], dp_table[row-1][col])
                else:
                    dp_table[row][col] = max(dp_table[row][col], dp_table[row-1][col]+dp_table[row][col-1], 
                    dp_table[row-1][col],dp_table[row][col-1])
           

    return dp_table[-1][-1]%1000000007 if dp_table[-1][-1] > 0 else 0