[프로그래머스] 레벨3 등굣길

https://programmers.co.kr/learn/courses/30/lessons/42898?language=java 

코딩테스트 연습 - 등굣길

 

최근에 DP를 활용한 문제를 좀 풀고 싶었고, 또 레벨3는 어느 정도의 난이도인지 궁금했는데 마침 레벨3 문제에 이게 있어서 도전해봤다.

일단 가장 먼저 생각했던 건 puddles 배열에 있는 값은 웅덩이(갈 수 없는 경로) 처리를 한 후, 벽에 딱 붙어있는 경로(i나 j가 1인 경우)를 먼저 1로 초기화해서 계산하는 방식이었다. 일반적인 케이스는 통과했던거 같지만 일부 TC를 통과하지 못했는데 생각해보니 웅덩이가 벽에 딱 붙어있을 경우를 생각하지 못했다.

따라서 초기화하는 부분을 없애고 대신 값을 더해주는 부분에 조건을 추가했다. 그리고 최종 리턴값 이외에도 arr 배열에 들어가는 모든 값들은 더하기 전에 한번씩 전부 MOD 연산자를 사용해야 한다.

100%해결하진 못했지만 그래도 접근방법이 매우 비슷해지고 있는걸로 봐서는 DP에 대한 이해도가 처음보다는 좀 높아진 것 같다.

 

 

class Solution
{
    public int solution(int m, int n, int[][] puddles)
    {
        int[][] arr = new int[n+1][m+1];
        arr[1][1] = 1;

        for(int i=0; i<puddles.length; i++)
        {
            arr[puddles[i][1]][puddles[i][0]] = -1;
        }
        
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(arr[i][j]==-1)
                {
                    continue;
                }
                if(arr[i-1][j]>0 && i-1>0)
                {
                    arr[i][j] += (arr[i-1][j])%1000000007;
                }
                if(arr[i][j-1]>0 && j-1>0)
                {
                    arr[i][j] += (arr[i][j-1])%1000000007;
                }
            }
        }
        
        return (arr[n][m])%1000000007;
    }
}