보행자 천국

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

코딩테스트 연습 - 보행자 천국

처음에는 밑에와 같이 DFS로 풀었더니 시간초과가 났다 그때서야 이문제가 DFS로 푸는 문제가 아니라는 것을 알게 되었다

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

int MOD = 20170805;

int dx[] = {1,0}; //아래
int dy[] = {0,1}; //오른쪽

int count;

void dfs(vector<vector<int>>& city_map, int x, int y, int n, int m, string way){
    
   // cout<<"hi"<<endl;
    if((x==m-1) && (y ==n-1)){
        count++;
        count%MOD;
        return;
    }
    
    if(city_map[x][y]==1){
        return;
    }
 
    
    if(city_map[x][y]==2 && way!="s"){
       if(way == "lr"){
            int nx = x+dx[1];
            int ny = y+dy[1];
           if(nx>=0 && nx<m && ny>=0 && ny<n){
            dfs(city_map,nx,ny,n,m,"lr");
           }
       } 
        else{
            int nx = x+dx[0];
            int ny = y+dy[0];
           if(nx>=0 && nx<m && ny>=0 && ny<n){
            dfs(city_map,nx,ny,n,m,"ud");
           }
        }
    }
    else if(city_map[x][y]==0 || way=="s"){
        for(int i=0; i<2; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx>=0 && nx<m && ny>=0 && ny<n){
            if(i==1){
                 dfs(city_map,nx,ny,n,m,"lr");
            }
            else{
                 dfs(city_map,nx,ny,n,m,"ud");
            }
        }
        }
    }
    
    return;
    
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    count =0;
    dfs(city_map,0,0,n,m,"s");
    answer = count;
    return answer;
}

생각해보니 이문제가 저번에 풀었던 등굣길 문제와 비슷하다는 것을 알게 되었다. 

spacefordeveloper.tistory.com/148?category=934243

등굣길

좀더 빨리 캐치해냈으면 좋았을 텐데 눈치없이 bfs로 푼것 같아 조금 아쉬운 부분이 있다. 

 

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

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    int dp[505][505][2]; //0: 오왼, 1: 위아래
    memset(dp,0,sizeof(dp));
    int MOD = 20170805;
    dp[1][1][0]=1; //시작지점은 무조건 1
    dp[1][1][1]=1;
    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){ //i 또는 j를 1부터 시작하도록 해야 i-1, j-1 seg fault 안남
            
            if(city_map[i-1][j-1]==0){
                dp[i][j][0] = (dp[i][j][0]+dp[i-1][j][1]+dp[i][j-1][0])%MOD; //기존 dp[i][j][0] 값에서 더해줘야지 기존 dp[1][1][0]=1 값을 포함시킬수 있음
                dp[i][j][1] = (dp[i][j][1]+dp[i-1][j][1]+dp[i][j-1][0])%MOD;
            }
            else if(city_map[i-1][j-1]==2){
                 dp[i][j][0] =  (dp[i][j][0]+dp[i][j-1][0])%MOD;
                 dp[i][j][1] = (dp[i][j][1]+dp[i-1][j][1])%MOD;
            }
            else{
                   dp[i][j][0]=0;
                   dp[i][j][1] =0;
            }
            
        }
        
    } 
    answer = dp[m][n][0];
    
    return answer;
}