오늘 풀어본 문제는 ⭐문제링크 이 문제이다!
1. 문제 설명
M*N만큼의 도로가 있다. 해당 격자는 다음과 같은 규칙을 가진다.
- 차량은 아래, 오른쪽으로만 이동한다.
- 0이라 써 있는 도로는 자유통행이다.
- 1이라 써 있는 도로는 갈 수 없다.
- 2라 써 있는 도로는 커브를 틀 수 없다.(직진만 가능하다.)
2. 문제 접근법
해당 문제는 최대 500*500의 격자를 가진다. 만약 해당 격자를 bfs나 dfs로 풀려 했다면 한 격자당 갈 수 있는 경우의 수 2개(아래로 가기, 오른쪽으로 가기)이다.
즉 경우의 수는 2^500이란 뜻이다.
처음에 dfs로 접근하다가 틀렸다^^ 이 문제는 dp로 풀어야 했다.
문제풀이법은 다음과 같다.
- 3차원 배열을 사용하여 아래로 가는 방향의 격자 하나, 오른쪽으로 가는 격자 하나로 구분한다.
- 해당 위치가 0이면, 오른쪽/아래 방향으로 경우의 수 +=전달
- 해당 위치가 1이면, 전달 x
- 해당 위치가 2면,
(현재 위치 기준)오른쪽 방향으로는 오른쪽으로 온 경우의 수만 전달,
(현재 위치 기준)아래쪽 방향으로는 아래쪽으로 온 경우의 수만 전달
3. 코드
위와 같은 규칙을 지켜 코드는 다음과 같이 작성했다.
class Solution {
int mod = 20170805;
static long [][][] dp;
public int solution(int m, int n, int[][] cityMap) {
dp = new long [2][m+1][n+1]; //0:아래, 1:오른쪽
dp[0][0][0]=1;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(cityMap[i][j]==0){
dp[0][i+1][j]+=(dp[0][i][j]+dp[1][i][j]);
dp[1][i][j+1]+=(dp[0][i][j]+dp[1][i][j]);
}else if(cityMap[i][j]==2){
dp[0][i+1][j]+=dp[0][i][j]; //아래쪽으로 온 경우의 수만 아래 방향으로 전달
dp[1][i][j+1]+=dp[1][i][j];//오른쪽으로 온 경우의 수만 오른쪽 방향으로 전달
}
}
}
return (int)((dp[0][m-1][n-1]+dp[1][m-1][n-1])%mod);
}
}그런데..? 틀렸다는 판단을 받았다. 아무리 생각해도 long과 int의 변환이 쎄해서 코드를 다음과 같이 고쳐보니..
class Solution {
int MOD = 20170805;
static int [][][] dp;
public int solution(int m, int n, int[][] cityMap) {
dp = new int [2][m+1][n+1]; //0:아래, 1:오른쪽
dp[0][0][0]=1;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(cityMap[i][j]==0){
dp[0][i+1][j]+=(dp[0][i][j]+dp[1][i][j])%MOD;
dp[1][i][j+1]+=(dp[0][i][j]+dp[1][i][j])%MOD;
}else if(cityMap[i][j]==2){
dp[0][i+1][j]+=dp[0][i][j]%MOD; //아래쪽으로 온 경우의 수만 아래 방향으로 전달
dp[1][i][j+1]+=dp[1][i][j]%MOD;//오른쪽으로 온 경우의 수만 오른쪽 방향으로 전달
}
}
}
return (dp[0][m-1][n-1]+dp[1][m-1][n-1])%MOD;
}
}이건 맞다는 판단이 나왔다.
아무래도... +=연산을 계속해서 해주다 보니 자료형을 long으로 썼다 해도 오버플로우가 나는 경향이 있는 것 같다.
즉 생각나는 경우의 수는 2가지이다.
1. +=연산을 통해 경우의 수가 long 자료형도 초과한 경우
2. 모듈러 연산을 했음에도 int 자료형에 담을 수 있는 수의 범위를 지나쳐서 형변환이 불가능했던 경우.
문제에서 모듈러 연산으로 답을 내라 하는 경우엔, 그냥 위 코드처럼 매 계산시 모듈러로 저장해줘야겠다는 교훈을 얻었다.
