[promgrammers] 등굣길

문제 링크입니다

🚀 [등굣길] Lv. 3 문제

웅덩이를 -1 로 표시하고 각종 조건을 따져주고 다이나믹 프로그래밍을 사용해 문제를 쉽게 해결할 수 있다.

💎 전체 코드는 다음과 같습니다.

#include <string>
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    int road[101][101];
    memset(road,0,sizeof(road)); // 0 초기화
    road[1][1] = 1;
    for(int i=0; i<puddles.size(); i++){
        int xpool = puddles[i][0];
        int ypool = puddles[i][1];
        road[ypool][xpool] = -1;
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(road[i][j] == -1)
                continue;
            // 위와 왼쪽 모두 막혔을때
            else if(road[i-1][j]== -1 && road[i][j-1]==-1) road[i][j] = -1;
            // 왼쪽만 막혔을 때
            else if(road[i][j-1]==-1 && road[i-1][j] !=-1) road[i][j]=road[i-1][j];
            // 위쪽만 막혔을 때
            else if(road[i-1][j]==-1 && road[i][j-1] !=-1) road[i][j]=road[i][j-1];
            // 막히지 않았을 떄
            else road[i][j] += (road[i-1][j] + road[i][j-1])%1000000007;
        }
    }
    answer = road[n][m];
    return answer;

}