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

bfs - 효율성 실패

ㅜㅜ

 

집이 우측 하단 맨 끝에 존재함, 오른쪽 또는 아래로만 이동함. -> 막힌 길을 빙 둘러서 가는 경우는 존재 X

=> bfs로 돌려도 답은 정확히 나옴 

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

#define X first
#define Y second
//최단 경로가 아니라, 최단 경로의 개수 ?
//경우의 수 -> 오른쪽으로 이동, 아래로 이동 
int dx[2]= {1,0};
int dy[2]= {0,1};

queue<pair<int,int>> Q;
int vis[103][103];
int board[103][103];

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    //m= 열 개수,n= 행 개수
    for(int i=0;i<puddles.size();i++){
       board[puddles[i][0]][puddles[i][1]] = -1; // 웅덩이 표시
    }
    Q.push({1,1});

    while(!Q.empty()){
        pair<int,int> cur = Q.front(); Q.pop();
        
        for( int j =0;j<2;j++){
            int nx =cur.X + dx[j];
            int ny =cur.Y + dy[j];
            
            if(nx > m|| ny>n) continue;
            if(nx == m && ny ==n){
                answer++;
            }
            if(board[nx][ny]==-1) continue;

            Q.push({nx,ny});
        }
    }
    
    return answer;
}

 

DP - 성공 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int cases[102][102]; // 열,행까지 오는데 가능한 경우의 수 , 만나면 더한다 
int water[102][102]; // 웅덩이 -1로 표시

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    //열, 행
    // 가능한 경우의 수 - > 오른쪽 이동 or 아래로 이동
        
    for(int i=0;i<puddles.size();i++){
        water[puddles[i][0]][puddles[i][1]] = -1; // 웅덩이 표시
    }
    
    //왼쪽값과 위의 값을 더해서 아래 값을 만들어낸다 
    cases[1][1]=1;
    
    for(int i=1;i<m+1;i++){ //열
        for(int j=1;j<n+1;j++){ //행
            if(water[i][j] != -1){
                if(i!=1||j!=1){
                    cases[i][j] = (cases[i-1][j]+cases[i][j-1]) % 1000000007;
                }  
            }
        }
    }
    return cases[m][n];
}