프로그래머스 - 등굣길 - DP - Java

1. 문제

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

2. 풀이

참고 풀이

DP는 풀어도 풀어도 어렵다 ㅜ

해당 풀이는 DFS, BFS 모두 시간초과가 발생한다.

❌틀린 풀이 - DFS

import java.util.*;

class Solution {
    int map[][];
    int moveX[] = {0, 1};
    int moveY[] = {1, 0};
    int answer = 0;
    int M;
    int N;
    public int solution(int m, int n, int[][] puddles) {
        map = new int[n][m];
        N = n;
        M = m;
        
        for(int i = 0; i < puddles.length; i++){
            map[puddles[i][1] - 1][puddles[i][0] - 1] = 1;
        }
        
        dfs(0, 0);
        
        return answer % 1000000007;
    }
    
    public void dfs(int x, int y){
        if(x == N-1 && y == M-1){
            //answer += (answer % 1000000007);
            answer += 1;
            return;
        }
        
        for(int i = 0; i < moveX.length; i++){
            int goX = x + moveX[i];
            int goY = y + moveY[i];
            
            if(goX < 0 || goY < 0 || goX >= N || goY >= M){
                continue;
            }
            
            if(map[goX][goY] == 1){
                continue;
            }
            
            dfs(goX, goY);
        }
    }
}

✨최단경로의 개수이면 -> DP일 확률이 높다!!

3. 전체 코드

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int dp[][] = new int[n+1][m+1];
        int mod = 1000000007;
        
        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; i++){
            for(int j = 1; j <= m; j++){
                if(dp[i][j] == -1)
                    continue;
                
                if(dp[i-1][j] > 0)
                    dp[i][j] += dp[i-1][j] % mod;
                
                if(dp[i][j-1] > 0)
                    dp[i][j] += dp[i][j-1] % mod;
            }
        }
        
        return dp[n][m] % mod;
    }
}