[프로그래머스] 보행자 천국 (JAVA)

문제 설명

카카오내비 개발자인 제이지는 시내 중심가의 경로 탐색 알고리즘 개발 업무를 담당하고 있다. 최근 들어 보행자가 자유롭고 편리하게 걸을 수 있도록 보행자 중심의 교통 체계가 도입되면서 도심의 일부 구역은 자동차 통행이 금지되고, 일부 교차로에서는 보행자 안전을 위해 좌회전이나 우회전이 금지되기도 했다. 복잡해진 도로 환경으로 인해 기존의 경로 탐색 알고리즘을 보완해야 할 필요가 생겼다.

도시 중심가의 지도는 m × n 크기의 격자 모양 배열 city_map으로 주어진다. 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다.

city_map[i][j]에는 도로의 상황을 나타내는 값이 저장되어 있다.

0인 경우에는 자동차가 자유롭게 지나갈 수 있다.
1인 경우에는 자동차 통행이 금지되어 지나갈 수 없다.
2인 경우는 보행자 안전을 위해 좌회전이나 우회전이 금지된다. (왼쪽에서 오던 차는 오른쪽으로만, 위에서 오던 차는 아래쪽으로만 진행 가능하다)

입력 형식

입력은 도시의 크기를 나타내는 m과 n, 그리고 지도를 나타내는 2차원 배열 city_map으로 주어진다. 제한조건은 아래와 같다.

1 <= m, n <= 500
city_map의 크기는 m × n이다.
배열의 모든 원소의 값은 0, 1, 2 중 하나이다.
출발점의 좌표는 (0, 0), 도착점의 좌표는 (m - 1, n - 1)이다.
출발점과 도착점의 city_map[i][j] 값은 0이다.

Code

class Solution {
    int MOD = 20170805;
    public int solution(int m, int n, int[][] cityMap) {
        int[][] dp = new int[m][n];
		dp[0][0] = 1;
		
		for(int i=0 ; i<m ; i++) {
			for(int j=0 ; j<n ; j++) {
				
				if(i==0 && j==0) continue;
				// 0일때만 기록한다.
				if(cityMap[i][j]==0) {
					// 왼쪽에서
					dp[i][j] = (dp[i][j]+getNum(cityMap, dp, i, j-1, false))%MOD;
					// 위에서
					dp[i][j] = (dp[i][j]+getNum(cityMap, dp, i-1, j, true))%MOD;
				}
			}
		}		
		return dp[m-1][n-1];
    }
    
    public int getNum(int[][] cityMap, int[][] dp, int i, int j, boolean up) {
		if(i<0 || i>=dp.length || j<0 || j>=dp[0].length || cityMap[i][j]==1) {
			return 0;
		}
		
		if(cityMap[i][j]==0) {
			return dp[i][j];
		} 
		
		int iMinus=0, jMinus=0;
		// 다음 2(조건통행)가 나올때까지 탐색
		while(i-iMinus-(up?1:0) >= 0 && j-jMinus-(up?0:1) >= 0 && cityMap[i-iMinus][j-jMinus]==2) {
			iMinus+=(up?1:0);
			jMinus+=(up?0:1);
		}
		
		return dp[i-iMinus][j-jMinus];
	}
    
}