[프로그래머스 Level 3] 보행자 천국 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/1832

프로그래머스

 

 

경우의 수를 찾는 문제이다. 처음에 dfs로 풀다가 m과 n이 꽤 큰 것을 보고 시간 초과가 날 거 같아 방식을 바꿨다.

한 지점 A가 있으면 왼쪽과 위쪽에 위치한 지점의 경우의 수를 더해주는 방식으로 해줬다. 이 때 좌회전 우회전 금지일 경우 한 칸 더 전으로 계산해주었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <memory.h>

using namespace std;

int MOD = 20170805;

//void dfs(int m, int n, int direct){
//    if(m>=realMap.size()||n>=realMap[0].size()){
//        return;
//    }
//    if(m==realMap.size()-1&&n==realMap.size()-1){
//        sum=(sum+1)%MOD;
//    }
//    if(realMap[m][n]==1){
//        return;
//    }else if(realMap[m][n]==2){
//        //direct가 1이면 아래, 2이면 오른쪽
//        if(direct==1){
//            dfs(m+1,n,1);
//        }else{
//            dfs(m,n+1,2);
//        }
//    }else{
//        dfs(m+1,n,1);
//        dfs(m,n+1,2);
//    }
//}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    int resultMap[500][500];
    memset(resultMap, 0, sizeof(resultMap));
    resultMap[0][0]=1;
    for(int i = 1; i<n; i++){
        if(city_map[0][i]==1){
            resultMap[0][i]=0;
        }else{
            resultMap[0][i]=resultMap[0][i-1];
        }
    }
    for(int i = 1; i<m; i++){
        if(city_map[i][0]==1){
            resultMap[i][0]=0;
        }else{
            resultMap[i][0]=resultMap[i-1][0];
        }
    }
    for(int i = 1; i<m; i++){
        for(int j=1; j<n; j++){
            if(city_map[i][j]==2){
                continue;
            }else if(city_map[i][j]==1){
                city_map[i][j]=0;
            }else{
                if(city_map[i][j-1]==2){
                    int tmp = 2;
                    while(j-tmp>=0&&city_map[i][j-tmp]==2){
                        tmp++;
                    }
                    if(j-tmp>=0){
                        resultMap[i][j]=(resultMap[i][j]+resultMap[i][j-tmp])%MOD;
                    }
                }else{
                    resultMap[i][j]=(resultMap[i][j]+resultMap[i][j-1])%MOD;
                }
                if(city_map[i-1][j]==2){
                    int tmp = 2;
                    while(i-tmp>=0&&city_map[i-tmp][j]==2){
                        tmp++;
                    }
                    if(i-tmp>=0){
                        resultMap[i][j]=(resultMap[i][j]+resultMap[i-tmp][j])%MOD;
                    }
                }else{
                    resultMap[i][j]=(resultMap[i][j]+resultMap[i-1][j])%MOD;
                }
            }
        }
    }
//    for(int i = 0 ; i<m; i++){
//        for(int j = 0 ; j<n; j++){
//            cout<<resultMap[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    return answer=resultMap[m-1][n-1];
}