> 문제
문제 : [보행자 천국]
> 문제풀이
자동차가 오른쪽 또는 아래로만 이동이 가능하기 때문에, 해당 위치에서 위,왼쪽 위치의 경로값을 더해가는 방식으로 구현하였다.
해당 노드에서 위 또는 왼쪽에 2가 있다면 그 방향으로 쭉쭉 타고가서 0인 값을 더하였다.
소스는 다음과 같다.
class Solution {
static int MOD = 20170805;
static boolean check(int x, int y, int[][] map){
if(x>=0 && y>=0 && x<map.length && y<map[x].length){
return true;
}else return false;
}
static int[][] dir = { { 0, -1 }, { -1, 0 } };
public int solution(int m, int n, int[][] cityMap) {
int[][] map = new int[m][n];
map[0][0] = 1;
int dx,dy;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
int tmp = 0;
if(cityMap[i][j] == 1) continue;
for(int d=0; d<2; d++){
dx = i + dir[d][0];
dy = j + dir[d][1];
if(check(dx,dy,cityMap)){
if(cityMap[dx][dy] == 0){
tmp += map[dx][dy];
}else if(cityMap[dx][dy] == 2){
while(check(dx, dy, map) && cityMap[dx][dy] == 2) {
dx+=dir[d][0];
dy+=dir[d][1];
}
tmp += check(dx, dy, map) && cityMap[dx][dy] == 0 ? map[dx][dy] : 0;
}
}
}
map[i][j] += (tmp % MOD);
}
}
return map[m-1][n-1] % MOD;
}
}
문제 출처 : Programmers