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

문제

집에서 학교까지 물이 잠긴 지역을 피해 가는 최단경로의 개수를 구한다.

---

접근

• dp 배열을 통해 각 위치까지 가는데 드는 최단 경로의 개수를 저장한다. 모두 0으로 초기화한다.
• 먼저 집이 있는 행과 열은 해당 위치까지 가는 최단 경로가 직진하는 경우 단 1개 뿐이므로 1로 설정한다.
  • 이때 주의할점은 집이 있는 행과 열에 웅덩이가 있는 경우는 해당 웅덩이 다음부터는 1로 설정을 멈추어야 한다!(웅덩이가 있으면 직진을 할 수 없으므로!!!) -> 이 부분을 고려안해서 맨 처음에 틀렸었다😕
• 나머지 위치에 대해서는 왼쪽과 위쪽의 최단 경로의 개수 값을 더하여 저장한다.
• 이 과정을 반복하면 학교가 있는 위치의 dp 값이 집에서 학교까지 물이 잠긴 지역을 피해 가는 최단 경로의 개수가 된다.

 

---

성공 코드(내 코드)

#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));
    for(int i=0; i<puddles.size(); i++){
        dp[puddles[i][1]][puddles[i][0]]=-1;
    }
    for(int i=1; i<=n; i++){
        if(dp[i][1]==-1) break;
        dp[i][1]=1;
    }
    for(int i=1; i<=m; i++){
        if(dp[1][i]==-1) break;
        dp[1][i]=1;
    }
    for(int i=2; i<=n; i++){
        for(int j=2; j<=m; j++){
            if(dp[i][j]==0){
                int way=0;
                if(i-1>0 && dp[i-1][j]>0) way+=dp[i-1][j];
                if(j-1>0 && dp[i][j-1]>0) way+=dp[i][j-1];
                dp[i][j]=way%1000000007;
            }
        }
    }
    answer=dp[n][m];
    
    return answer;
}

 

🤨

근데 %1000000007을 값을 리턴하기 전에 해주니 효율성 초과가 떴다.. 왤까???

---

후기

최단경로의 개수를 구하는 문제는 고딩 때 많이 풀었었는데, 코테 연습 문제로 만나니 반가웠다😀 덕분에 재밌게 풀었다~!~!~!