[프로그래머스] 등굣길

programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

---

풀이)

dp문제이다.

1.puddle에 있는 위치좌표들을 maze배열에 체크를 해둔다.( 주의해야 할 점은 puddles도 m,n순서이므로 신경써주자)

2.dp배열을 max+1만큼 할당을 해준다.

3.dp[1][1](시작점)은 1로 해둔다. 왜냐하면 초반 초기화를 하지 않기위해서이다.

4.물웅덩이가 있는 좌표라면, 해당 좌표까지 가는 최단경로는 없으므로, 해당dp[i][j]=0이 된다.

5.dp[i][j]는, i,j좌표까지 올 수 있는 최단 경로의 수 이므로 dp[i][j-1]에서 내려오는 경우의수+dp[i-1][j]에서 오른쪽으로 이동하는 경우의 수가 된다.

 

수행시간)

모든 좌표를 탐색하므로 O(M*N)이 된다.

 

코드)

#include <string>
#include <vector>

using namespace std;

bool maze[101][101]={0};
int dp[101][101]={0};

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    for(int i=0;i<puddles.size();i++){
        maze[puddles[i][1]][puddles[i][0]]=true;
    }
    dp[1][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i==1&&j==1) continue;
            if(!maze[i][j]){
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007;
            }
        }
    }
    answer=dp[n][m];
    
    return answer;
}

 

실행결과)