[프로그래머스] 등굣길 (Java)

문제

 

코딩테스트 연습 - 등굣길

 

풀이

0. 문제 해석

1. 그 위치로 갈 수 있는 경로의 수를 저장할 m*n (n*m) 크기의 dp 배열을 만든다.
2. 물에 잠긴 지역을 임의의 숫자(-1)로 표시해준다.
3. 시작점의 dp는 1로 지정해준다.
4. 전체탐색하면서 자신의 왼쪽과 위에 있는 위치가 물에 잠긴 지역이 아니라면 dp 값을 더해서 현재위치에 기록한다. 
5. 학교가 있는 좌표의 dp 값을 출력한다.

 

dp로 풀 수 있는 문제이다.

그런데 하나 주의할점이

대부분 문제는 행의 갯수, 열의 갯수 순으로 주어지는 경우가 많은데

이 문제에서는 m이 열의 갯수, n이 행의 갯수이므로 잘 생각해서 계산해야한다.

 

 

1. 전체 코드

// [프로그래머스] 등굣길 (Java)
class Solution {
    static int[][] dp;
    
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        
        dp = new int[n][m];
        for(int i = 0; i < puddles.length; i++){
            int y = puddles[i][0] - 1;
            int x = puddles[i][1] - 1;
            dp[x][y] = -1;
        }
        
        dp[0][0] = 1;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                
                if(dp[i][j] == -1) {
                    continue;
                }
                
                if(j != 0){
                    if(dp[i][j - 1] != -1){
                       dp[i][j] += dp[i][j - 1];  
                    }
                }
                if(i != 0){
                    if(dp[i - 1][j] != -1){
                        dp[i][j] += dp[i - 1][j];
                    }
                }
                
                dp[i][j] %= 1000000007;
            }
        }
        
        answer = dp[n - 1][m - 1] % 1000000007;
        
        return answer;
    }
}