문제 설명 및 제한사항
카카오내비 개발자인 제이지는 시내 중심가의 경로 탐색 알고리즘 개발 업무를 담당하고 있다. 최근 들어 보행자가 자유롭고 편리하게 걸을 수 있도록 보행자 중심의 교통 체계가 도입되면서 도심의 일부 구역은 자동차 통행이 금지되고, 일부 교차로에서는 보행자 안전을 위해 좌회전이나 우회전이 금지되기도 했다. 복잡해진 도로 환경으로 인해 기존의 경로 탐색 알고리즘을 보완해야 할 필요가 생겼다.
도시 중심가의 지도는 m × n 크기의 격자 모양 배열 city_map으로 주어진다. 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다.
city_map[i][j]에는 도로의 상황을 나타내는 값이 저장되어 있다.
•
0인 경우에는 자동차가 자유롭게 지나갈 수 있다.
•
1인 경우에는 자동차 통행이 금지되어 지나갈 수 없다.
•
2인 경우는 보행자 안전을 위해 좌회전이나 우회전이 금지된다. (왼쪽에서 오던 차는 오른쪽으로만, 위에서 오던 차는 아래쪽으로만 진행 가능하다)
도시의 도로 상태가 입력으로 주어졌을 때, 왼쪽 위의 출발점에서 오른쪽 아래 도착점까지 자동차로 이동 가능한 전체 가능한 경로 수를 출력하는 프로그램을 작성하라. 이때 가능한 경로의 수는 컴퓨터가 표현할 수 있는 정수의 범위를 넘어설 수 있으므로, 가능한 경로 수를 20170805로 나눈 나머지 값을 출력하라.
아이디어 및 해결 방법
어떤 칸까지 오는 경우의 수는 해당 칸의 왼쪽에서 오는 경우의 수와, 해당 칸의 위쪽에서 오는 경우의 수를 합쳐서 구할 수 있다. 이 때, 도로 상황에 따라서 경우를 나누어 처리해주어야 한다.
1.
(i, j) 칸이 통행 금지 칸 (1)인 경우
해당 칸까지 오는 경우의 수는 0이다. 못 오니까. continue 해서 무시하고 넘어가면 된다.
2.
(i, j) 칸 왼편으로/위편으로 좌/우회전 금지 칸(2)들이 연속된 경우 (없을 경우도 이 경우에 포함한다. 편의 상)
왼편/위편에서 처음으로 2가 아닌 값이 나오는 칸의 경우의 수를 받아와서 더해야 한다. while문을 활용하면 된다. 왼쪽 끝, 위쪽 끝을 넘어가면(즉, 왼쪽/위쪽 끝까지 내리 2인 경우) 해당 값은 0으로 처리한다.
이제, 값을 채워나가면 된다. MOD로 나눠주어야 함에 유의하자.
코드
#include <vector>
using namespace std;
int MOD = 20170805;
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
vector<vector<int>> dp;
for (int i = 0; i < m; i++) {
vector<int> v;
for (int j = 0; j < n; j++) {
v.push_back(0);
}
dp.push_back(v);
}
dp[0][0] = 1;
for (int i = 1; i < m; i++) {
if (city_map[i][0] == 1) continue;
dp[i][0] = dp[i-1][0];
}
for (int j = 1; j < n; j++) {
if (city_map[0][j] == 1) continue;
dp[0][j] = dp[0][j-1];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (city_map[i][j] == 1) continue;
int k = 1;
while (i-k >= 0 && city_map[i-k][j] == 2) k++;
int up = i-k < 0 ? 0 : dp[i-k][j];
k = 1;
while (j-k >= 0 && city_map[i][j-k] == 2) k++;
int left = j-k < 0 ? 0 : dp[i][j-k];
dp[i][j] = (left + up) % MOD;
}
}
return dp[m-1][n-1] % MOD;
}
C++
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges