[프로그래머스] Level 3. 보행자 천국

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

 

 

3차 배열 map을 선언한다.

map[i][j][0] = i,j 지점에서 아래로 이동할 수 있는 경우의 수

map[i][j][1] = i,j 지점에서 오른쪽로 이동할 수 있는 경우의 수 

 

차례대로 도시를 루프하면서, 만약 이동이 모두 가능하다면 왼쪽에서오는 경우의 수 + 위에서 부터 오는 경우의 수를 더하는 것이 i,j 에서 이동할 수 있는 경우이다.

map[i-1][j][0] = 내 위로부터 아래로 내려오는경우

map[i][j-1][1] = 내 왼쪽에서부터오는경우 

 

만약 모든 통행이 허가된다면 map[i][j] 에서 오른쪽, 아래로 가는 경우는 동일할 것이고, 값은 map[i-1][j][0] + map[i][j-1][1] 일것이다.

만약 꺾이는 통행이 금지된다면, map[i][j] 에서  오른쪽으로 가는 경우는 map[i][j-1][1] 이고, 아래로 가는 경우는 map[i-1][j][0] 이다.

 

#include <vector>

using namespace std;

int MOD = 20170805;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
  
    vector<vector<vector<int>>> map(m,vector<vector<int>>(n, vector<int>(2,0)));
    map[0][0][0] = 1; //i,j 지점에서 아래로 가는 경우의 수 저장.
    map[0][0][1] = 1; //i,j 지점에서 오른쪽으로 가는 경우의 수 저장.
    
    for(int i=0; i<m; i++){
        for(int j=0; j<n;j++ ){
            if(i==0 && j==0) continue;
            if(city_map[i][j] == 1) continue;
            if(city_map[i][j] == 0){ //통행 자유. 
                int value = 0;
                if(i-1 >=0 ) value += map[i-1][j][0];
                if(j-1 >=0 ) value += map[i][j-1][1];
                
                map[i][j][0] = map[i][j][1] = (value % MOD);
            }
            else if(city_map[i][j]==2){
                if(i-1 >=0) map[i][j][0] = map[i-1][j][0] % MOD; 
                if(j-1 >=0) map[i][j][1] = map[i][j-1][1] % MOD;
            }
        }
        
       
    }
    
    return (map[m-2][n-1][0] + map[m-1][n-2][1]) % MOD;
    
}