보행자 천국 : https://school.programmers.co.kr/learn/courses/30/lessons/1832
Problem
Solve
자동차의 이동은 배열을 기준으로 아래와 오른쪽으로만 이동이 가능합니다.
그리고 목적지까지 이동이 가능한 경로 개수를 구해야하는데, cityMap[i][j]가 2인 경우 한쪽 방향으로만 이동이 가능합니다. 왼쪽 방향에서 해당 좌표로 접근하는 경우와 위쪽 방향에서 접근했을때의 경우를 구해야합니다.
접근 방향에 따른 이동 가능한 개수를 저장하는 dp를 사용할수 있습니다.
처음에는 재귀함수를 이용하여 dp에 값을 갱신하면서 구하였었는데, 어느 부분에서 값을 잘못 불러오는 바람에 찾지못하고 다른 분의 풀이를 참조하였습니다.
dp[i][j][0]과 dp[i][j][1]을 이용합니다.
0은 위 방향에서 접근할때 해당 좌표에서 목적지까지의 경로 수, 1은 왼쪽 방향에서 접근할때 해당 좌표에서 목적지까지의 경로 수를 나타내고 있습니다.
cityMap[i][j] == 0인 경우
- 해당 좌표에서 아래쪽과 오른쪽으로 이동이 가능합니다.
- 그렇기 때문에 해당 좌표에서 아래쪽인
cityMap[i+1][j]와 오른쪽인cityMap[i][j+1]로 이동이 가능하게 됩니다.
cityMap[i+1][j]에서는 위쪽에서 접근을 한 경우이기 때문에dp[i+1][j][0]이cityMap[i][j]에서cityMap[i+1][j]로 접근했을때 목적지로 접근 가능한 경우의 수가 됩니다. - 마찬가지로
ciytMap[i][j+1]에서는 왼쪽에서 접근을 한 경우이기 때문에dp[i][j+1][1]이cityMap[i][j]에서cityMap[i][j+1]로 접근했을때 목적지로 접근 가능한 경우의 수가 됩니다.
cityMap[i][j] == 2인 경우
- 해당 좌표로 접근한 방향으로 다음 이동이 가능합니다.
- 해당 좌표로 위쪽에서 접근하였다면 해당 좌표에서 아래쪽으로만 이동이 가능하고 왼쪽에서 접근하였다면 해당 좌표에서 오른쪽으로만 이동이 가능합니다.
cityMap[i][j]로cityMap[i-1][j]에서 접근하였다면cityMap[i+1][j]로만 이동이 가능하고,cityMap[i][j-1]에서 접근하였다면cityMap[i][j+1]로만 이동이 가능합니다.
이를 통해 점화식을 세울수 있습니다.
cityMap[i][j] == 0인 경우
dp[i][j][0] = dp[i+1][j][0] + dp[i][j+1][1]dp[i][j][1] = dp[i+1][j][0] + dp[i][j+1][1]- 어느 방향으로 접근하여도 해당 좌표의 아래쪽방향(
[i+1][j])에서는 위쪽에서 접근하는 것이기 때문에dp[i][j][0]과dp[i][j][1]에dp[i+1][j][0]을, 오른쪽방향([i][j+1])에서는 왼쪽에서 접근하는 것이기 때문에dp[i][j+1][1]을 더해주는 것입니다.
cityMap[i][j] == 2인 경우
dp[i][j][0] = dp[i+1][j][0]dp[i][j][1] = dp[i][j+1][1]- 위쪽에서 접근(
dp[i][j][0])했다면 해당 좌표의 아래쪽(dp[i+1][j][0])으로만, 왼쪽에서 접근(dp[i][j][1])했다면 해당 좌표의 오른쪽(dp[i][j+1][1])으로만 이동이 가능합니다.
cityMap[i][j] == 1인 경우는 접근이 불가능하므로 dp[i][j][0] = dp[i][j][1] = 0입니다.
목적지인 cityMap[m-1][n-1]은 어느 방향으로 접근하여도 접근 가능 경우는 1이기 때문에 dp[m-1][n-1][0] = dp[m-1][n-1][1] = 1로 초기화 해주어야합니다.
경우의 수가 커질수도 있다고 했기 때문에 20170805를 갱신해줄때마다 나머지를 구해줍니다.
출발지점 dp[0][0][0]에 목적지까지의 접근 가능한 경우의 수가 저장되어있습니다. (dp[0][0][1]도 동일합니다.)
Code
class Solution {
int MOD = 20170805;
public int solution(int m, int n, int[][] cityMap) {
int[][][] dp = new int[m+1][n+1][2];
dp[m-1][n-1][0] = dp[m-1][n-1][1] = 1;
for(int i=m-1;i>=0;i--){
for(int j=n-1;j>=0;j--){
if(cityMap[i][j] == 0){
dp[i][j][0] += (dp[i+1][j][0]+dp[i][j+1][1])%MOD;
dp[i][j][1] += (dp[i+1][j][0]+dp[i][j+1][1])%MOD;
}
else if(cityMap[i][j] == 2){
dp[i][j][0] += (dp[i+1][j][0])%MOD;
dp[i][j][1] += (dp[i][j+1][1])%MOD;
}
else{
dp[i][j][0] = 0;
dp[i][j][1] = 0;
}
}
}
return dp[0][0][0];
}
}Result
dp를 생각할때 항상 재귀쪽을 먼저 생각하게 되는것 같은데, 특정 지점에서의 방향의 값을 구할때 반복문으로 접근하는 방법이 있다는 것을 기억하자.
Reference
