카카오내비 개발자인 제이지는 시내 중심가의 경로 탐색 알고리즘 개발 업무를 담당하고 있다. 최근 들어 보행자가 자유롭고 편리하게 걸을 수 있도록 보행자 중심의 교통 체계가 도입되면서 도심의 일부 구역은 자동차 통행이 금지되고, 일부 교차로에서는 보행자 안전을 위해 좌회전이나 우회전이 금지되기도 했다. 복잡해진 도로 환경으로 인해 기존의 경로 탐색 알고리즘을 보완해야 할 필요가 생겼다.
도시 중심가의 지도는m × n크기의 격자 모양 배열city_map으로 주어진다. 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다.
city_map[i][j]에는 도로의 상황을 나타내는 값이 저장되어 있다.
0인 경우에는 자동차가 자유롭게 지나갈 수 있다.
1인 경우에는 자동차 통행이 금지되어 지나갈 수 없다.
2인 경우는 보행자 안전을 위해 좌회전이나 우회전이 금지된다. (왼쪽에서 오던 차는 오른쪽으로만, 위에서 오던 차는 아래쪽으로만 진행 가능하다)
도시의 도로 상태가 입력으로 주어졌을 때, 왼쪽 위의 출발점에서 오른쪽 아래 도착점까지 자동차로 이동 가능한 전체 가능한 경로 수를 출력하는 프로그램을 작성하라. 이때 가능한 경로의 수는 컴퓨터가 표현할 수 있는 정수의 범위를 넘어설 수 있으므로, 가능한 경로 수를20170805로 나눈 나머지 값을 출력하라.
제한사항
입력 형식
입력은 도시의 크기를 나타내는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이다.
출력 형식
출발점에서 도착점까지 이동 가능한 전체 경로의 수를20170805로 나눈 나머지를 리턴한다.
풀이
입출력 예시
풀이
이 문제는 일반적인 탐색 기법으로 결과를 도출해내는 것이 아니었다. 이전에 풀었던 경주로 건설 문제와 같이 3차원 배열로 선언해서 왔던 방향에 대한 정보를 알고 있어야한다. 그 이유는, 도로에서 2로 되어있는 부분은 왔던 방향으로만 진행할 수 있다고 되어있기 때문이다.
이후에는 반복문을 돌면서 경우의 수를 세어준다. 이 부분은 이전에 풀었던 등굣길 문제와 비슷했다.
#include <vector>
using namespace std;
int MOD = 20170805;
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
int answer = 0;
vector<vector<vector<long long>>> dp(m + 1, vector<vector<long long>> (n + 1, vector<long long> (2, 0)));
dp[1][1][0] = 1;
dp[1][1][1] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (city_map[i - 1][j - 1] == 0) {
dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][0] + dp[i][j - 1][1]) % MOD;
dp[i][j][1] = (dp[i][j][1] + dp[i - 1][j][0] + dp[i][j - 1][1]) % MOD;
}
else if (city_map[i - 1][j - 1] == 1) {
dp[i][j][0] = 0;
dp[i][j][1] = 0;
}
else {
dp[i][j][0] = dp[i - 1][j][0] % MOD;
dp[i][j][1] = dp[i][j - 1][1] % MOD;
}
}
}
answer = dp[m][n][0] % MOD;
return answer;
}
