[C++/프로그래머스] 등굣길

✅ LV. 3
🔖 DP

✏️ 1차 솔루션

DFS 로 풀이
1. (0,0) 에서 출발해 벽일 경우, 물 있을 경우 제외하고 오른쪽, 아래쪽으로 이동
2. (m,n) 에 도착하면 최단경로가 아니면 최단경로로 갱신, 최단경로와 동일하면 answer++

🚨 1차 trouble

시간 너무 오래 걸리고 효율성 오류

✏️ 최종 솔루션

각 노드를 지나가는 경로들을 count 해줘서 저장해나가기
최단경로를 찾아야 하지만 오른쪽, 아래쪽으로 밖에 못가니까 최단경로로 갈 수 밖에 없음

1. 이전노드의 경로 개수를 현재 노드에 저장하기 ➡️ 이전 노드를 지나왔다면 현재 노드도 지나갈 것이기 때문
2. 마지막 노드 (m,n) 에 저장된 거리가 answer 이 됨

📌 self feedback

진짜 웬만하면 벡터 쓰자^^

dp 점화식 예시
dp[i][j] = dp[i-1][j] + dp[i][j-1]

✏️ 최종 code

#include <string>
#include <vector>

using namespace std;


int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    dp[1][1]=1;
    
    for(int i=0;i<puddles.size();i++) dp[puddles[i][1]][puddles[i][0]]=-1;

    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            int a=0;
            int b=0;
        
            if(dp[i][j]==-1) continue;
            
            if(dp[i-1][j]!=-1) a=dp[i-1][j];
            if(dp[i][j-1]!=-1) b=dp[i][j-1];
            
            dp[i][j]+=(a+b)%1000000007;
        }
        
    }
    
    return dp[n][m];
}