보행자 천국

https://programmers.co.kr/learn/courses/30/lessons/1832

이문제를 처음에 별생각없이 BFS 로 풀어서 테스트케이스는 맞았으나 시간초과뜸.

#include <vector>
#include <queue>

using namespace std;
int arr[501][501] = { -1, };
int chk[501][501] = { -1 };
int dirX[2] = { 1,0 };//X진행방향
int dirY[2] = { 0,1 };//Y진행방향
int M(0);
int N(0);
int answer(0);

int MOD = 20170805;

void bfs(int y, int x)
{
	queue<pair<int, int>> qTemp;
	qTemp.push(make_pair(y, x));

	while (!qTemp.empty())
	{
		int y = qTemp.front().first;
		int x = qTemp.front().second;
		
		qTemp.pop();
		for (int i = 0; i < 2; i++)
		{
			int ny = y + dirY[i];
			int nx = x + dirX[i];
			if (ny >= 0 && ny < M && nx >= 0 && nx < N && arr[ny][nx] != 1)
			{
				if(arr[ny][nx] == 2 && y == ny && x == nx - 1 && nx - 1 >= 0 && nx+1<N)//오른쪽으로 가는 경우
				{
					qTemp.push(make_pair(ny, nx+1));
				} 
				else if (arr[ny][nx] == 2 && x == nx && y == ny - 1 && ny - 1 >= 0 && i == 1 &&ny+1<M)
				{
					qTemp.push(make_pair(ny+1, nx ));
				}
				else if (arr[ny][nx] == 0)
 				{
					qTemp.push(make_pair(ny, nx));
				}
					
					
				

				if (ny == M - 1 && nx == N - 1)
				{
					answer++;
				}
			}
		}
	}
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
	M = m; N = n;
	for (int i = 0; i < city_map.size(); i++)
	{
		for (int j = 0; j < city_map[0].size(); j++)
		{
			arr[i][j] = city_map[i][j];
			chk[i][j] = 0;// 아직 방문안함.
		}
	}

	bfs(0, 0);



	return answer;
}
 

int main()
{
	int m = 3;
	int n = 6;
	vector<vector<int>> vTemp = { {0, 2, 0, 0, 0, 2},{0, 0, 2, 0, 1, 0},{1, 0, 0, 2, 2, 0} };
	int iTemp = solution(m, n, vTemp);

	return 0;
}

이렇게 풀면 안된다는걸 느껴야 하는데, 지금 최단거리 및 거리방문 chk[][]을 하지 않았다.
방법이 몇가지나 되는가?(이전경로 거쳐서 가므로 방법 개수가 엄청나게 많아질 수 있음)
이걸 DP로 접근해야 한다고 아는게 중요하다.

정답소스

#include <vector>
using namespace std;

int MOD = 20170805;

int solution(int m, int n, vector<vector<int>> city_map) {
	int right[501][501];
	int down[501][501];

	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			right[i][j] = 0;
			down[i][j] = 0;
		}
	}

	for (int x = 1; x <= m; x++) {
		for (int y = 1; y <= n; y++) {
			int type = city_map[x - 1][y - 1];
			if ((x == 1) && (y == 1)) {
				right[x][y] = 1;
				down[x][y] = 1;
			}
			else if (type == 0) {
				right[x][y] = (right[x][y - 1] + down[x - 1][y]) % MOD;
				down[x][y] = (right[x][y - 1] + down[x - 1][y]) % MOD;
			}
			else if (type == 1) {
				right[x][y] = 0;
				down[x][y] = 0;
			}
			else if (type == 2) {
				right[x][y] = right[x][y - 1];
				down[x][y] = down[x - 1][y];
			}
		}
	}
	return right[m][n];
}

array를 x y 1시작부터 한 이유는 boundary계산의 편이성을 위하기 때문이다.
array i=0; j=0일때는 0으로 처리하는 특징이 있음.