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

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

프로그래머스

 

 

이 문제에서 중요한건 최단 거리가 되기위한 조건이다.

 

 

목적지가 최하단의 가장 우측에 있으므로 최단 거리로 이동하기 위해서는 오른쪽으로 가거나, 아래로 가야한다.

 

만약 경로중 위로가거나 왼쪽으로 간다면 그것은 최단 경로에 포함이 안된다.

 

따라서  dp배열에 오른쪽으로 가거나 왼쪽으로 가는 경우를 저장하여 최종 목적지까지 가는 경우의 수를 더해줬다.

 

물 웅덩이는 dp 배열에 -1로 저장하여 방문을 막았다.

 

<정답 코드>

import java.util.*;

class Solution {

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

 

느낀점 : dp 문제를 더 많이 풀어봐야겠다...