프로그래머스 - 등굣길

전형적인 dp 문제이다. 그래서 해답 또한 간단하다.

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        final int mod  = 1000000007;
        
        int[][] map = new int[n+1][m+1];
  
        for (int i=0;i<puddles.length;i++) {
            int r = puddles[i][1];
            int c = puddles[i][0];
            map[r][c] = -1;
        }     
        
        map[1][1]=1;
        
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) {
                
                if(map[i][j] == -1) 
                    continue;
                
                if(map[i - 1][j] > 0) 
                    map[i][j] +=  map[i - 1][j] % mod;
                
                if(map[i][j - 1] > 0) 
                    map[i][j] +=   map[i][j - 1] % mod;
            }
        }
        

        return map[n][m]% mod;
    }
}

해답

웅덩이는 -1로 만들어주고 시작값은 1로 준다. 이후 for문을 도는데 map[i-1][j],map[i][j-1]중에 웅덩이가 있다면 웅덩이가 아닌 쪽의 값을 그대로 map[i][j]에 넣어준다. 이런 방식으로 끝까지 가면 정답이 나온다.

위에서 쉽다고 했지만 문제를 대충 읽어서 다르게 이해하여 시간이 생각이상으로 오래 걸렸다. 문제를 꼼꼼히 읽는 습관을 길러야 할 것 같다.

출처: 프로그래머스 알고리즘 - 등굣길