문제 요약
- m × n 크기의 격자 모양 배열 city_map이 주어진다.
- 자동차는 city_map에서 오른쪽 혹은 아래 방향으로 한 칸씩 이동 가능하다.
- city_map[i][j]에는 도로의 상태를 나타내는 값이 저장되어 있다.
- 0인 경우에는 자유롭게 이동 가능
- 1인 경우에는 통행 금지
- 2인 경우에는 자회전 or 우회전 금지
(왼쪽에서 오던 차는 오른쪽으로만,
위에서 오던 차는 아래로만 이동 가능)
위에 같은 상황에서 city_map[0][0]에서 city_map[m - 1][n - 1]까지 이동 가능한 전체 경로의 수를 20170805로 나눈 나머지 값을 출력하는 문제입니다.
문제 분해
우선, 좌/우회전 금지 규칙을 무시하고 간단하게 답이 될 수 있는 경로의 수를 생각해 보면 다음과 같습니다.
city_map[m - 1][n - 1]에 도착할 수 있는 경로의 수를 path[m - 1][n - 1]이라고 하겠습니다. 자동차는 오른쪽 혹은 아래로만 이동 가능하기 때문에, path[m - 1][n - 1]의 값은 path[m - 1][n - 2]와 path[m - 2][n - 1]의 합입니다.
같은 논리로, path[m - 1][n - 2] = path[m - 1][n - 3] + path[m - 2][n - 2],
path[m - 2][n - 1] = path[m - 2][n - 2] + path[m - 3][n - 1]입니다.
이런 식으로 문제를 계속 축소해 나가다 보면, path[0][0]이 1이라는 사실을 이용해 바로 부문 문제의 해를 구할 수 있는 path[0][1]이나 path[1][0]까지 도달하게 됩니다.
각 부분문제를 해결하기 위해서는, 자신의 바로 위, 그리고 왼쪽 부분 문제의 해를 이용하기 때문에, [0][0]부터 [0][n - 1]까지 순서대로 해결한 후 다음 행의 문제를 해결하거나, 반대로 [0][0]부터 [m - 1][0]까지 순서대로 해결한 후 다음 열의 문제를 해결하는 식으로 진행하면 됩니다.
여기까지 고려했을 때,
(0 <= i <= m, 0 <= j <= n)
1. city_map[i][j]가 1인 경우
path[i][j] = 0
2. city_map[i][j]가 1이 아닌 경우
path[i][j] = path[i - 1][j] + path[i][j - 1]
라는 식으로 해결할 수 있겠지만, 무시해 두었던 조건인 좌/우회전 금지 규칙을 적용시켜야 합니다.
해당 규칙은 도로의 상태값이 2인 경우, 이동하던 방향으로 직진해야 한다는 것입니다. 따라서, path[i][j] 의 값을 구하기 위해서는, city_map[i - 1][j] 혹은 city_map[i][j - 1] 의 상태가 2였는지 먼저 검사해야 하고, 만약 2였다면 직진하는 경로만 부분해에 포함시켜야 하므로, path[i - 1][j] 혹은 path[i][j - 1] 을 둘로 나누어, 위에서 도착한 경로와 아래에서 도착한 경로의 수를 따로 유지해야 합니다.
path를 2차원 배열이 아닌 3차원 배열 path[m][n][2]로 정의하여,
city_map[i][j]지점에 왼쪽으로부터 들어온 경로의 수를 path[i][j][0]에,
city_map[i][j]지점에 위족으로부터 들어온 경로의 수를 path[i][j][1]에 저장하면 됩니다.
위에서 정리했던 식 2번을 다음과 같이 바꿀 수 있습니다.
- city_map[i][j]가 1이 아닌 경우
- city_map[i][j - 1]가
- 0일 때,
path[i][j][0] = path[i][j - 1][0] + path[i][j - 1][1]- 2일 때,
path[i][j][0] = path[i][j - 1][0]
- city_map[i - 1][j]가
- 0일 때,
path[i][j][1] = path[i - 1][j][0] + path[i - 1][j][1]- 2일 때,
path[i][j][1] = path[i - 1][j][1]
위와 같은 식을 이용해 부분문제를 해결하면서, 문제에 제시된대로 20170805로 나눈 나머지를 path[i][j][0]과 path[i][j][1]에 저장시키고, 최종적으로 path[m - 1][n - 1][0] + path[m - 1][n - 1][1]을 20170805로 나눈 나머지를 반환하면 됩니다.
코드(JAVA)
class Solution {
int MOD = 20170805;
public int solution(int m, int n, int[][] cityMap) {
int[][][] path = new int[m][n][2];// 0 - 왼쪽에서 오는 경우, 1 - 위에서 오는 경우
for(int i = 0; i < m; i++){
if(cityMap[i][0] == 1) break;
path[i][0][1] = 1;
}
for(int i = 0; i < n; i++){
if(cityMap[0][i] == 1) break;
path[0][i][0] = 1;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
if(cityMap[i][j] == 1) continue;
//직진으로 오는 경우
path[i][j][0] = path[i][j - 1][0]; //왼쪽
path[i][j][1] = path[i - 1][j][1]; //위쪽
//방향을 틀어서 오는 경우
if(cityMap[i][j - 1] != 2){ //왼쪽
path[i][j][0] += path[i][j - 1][1];
}
if(cityMap[i - 1][j] != 2){ //위쪽
path[i][j][1] += path[i - 1][j][0];
}
path[i][j][0] %= MOD;
path[i][j][1] %= MOD;
}
}
return (path[m - 1][n - 1][0] + path[m - 1][n - 1][1]) % MOD;
}
}