프로그래머스 Level 3 보행자천국

보행자천국 (프로그래머스 Level 3)

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

처음에는 BFS로 풀었으나
시간초과가 발생하여
고민하던 중 ‘DP’로 풀어야 겠다는 점은 확인할 수 있었다

1. 특정한 좌표 x,y 에 도달하기 위하여
   x -1, y 와 x, y-1의 좌표를 확인하여 두 위치의 경로의 수를 더한다
   
2. 해당 좌표가 장애물인 경우,
   ‘수직’ 도달이 가능한 좌표와(x, y-1)
   ‘수평’ 도달이 가능한 좌표를(x - 1, y)
   나누어 저장한다
   
3. 최종 좌표에서 값을 합하여 준다
   

개인적으로 ‘수직’과 ‘수평’에 대한 분리를 제대로 하지 못해
결국 실패하게 된 문제이다

ps) 프로그래머스 ai 추천 문제를 요새 푸는 중인데
내가 dp가 약해서 그런지는 몰라도 dp 문제가 굉장히 자주 나오는 느낌이다
그래도 이번 문제는 dp를 사용할 수 있겠다는 점은 느꼈으나
그 응용력이 아직 부족하다는 점을 느낄 수 있었다

Code

#include <vector>
using namespace std;

// 최종 결과를 20170805로 나눈 나머지를 반환하기 위한 MOD 값
int MOD = 20170805;

int solution(int m, int n, vector<vector<int>> city_map) {
	int answer = 0;
	// (y, x, 0)은 수평 이동, (y, x, 1)은 수직 이동으로 도달한 경로의 수를 저장할 3차원 DP 배열
	vector<vector<vector<long long>>> dp(m + 1, vector<vector<long long>>(n + 1, vector<long long>(2)));

	// 첫 행 초기화
	for (int y = 0; y < m; y++)
	{
		// 첫 열에 장애물이 있다면 더 이상 진행할 수 없음
		if (city_map[y][0] == 1)
			break;
		// 수직 이동으로 도달할 수 있는 경로의 수는 1
		dp[y][0][1] = 1;
	}

	// 첫 열 초기화
	for (int x = 0; x < n; x++)
	{
		// 첫 행에 장애물이 있다면 더 이상 진행할 수 없음
		if (city_map[0][x] == 1)
			break;

		// 수평 이동으로 도달할 수 있는 경로의 수는 1
		dp[0][x][0] = 1;
	}

	// 나머지 도시 지도 탐색
	for (int y = 1; y < m; y++)
	{
		for (int x = 1; x < n; x++)
		{
			// (y-1, x)가 장애물이 아니라면
			if (city_map[y - 1][x] == 0)
			{
				// (y, x)에 도달하는 수직 이동 경로의 수 갱신
				// 이 위치에는 수직, 수평이 모두 올 수 있음
				dp[y][x][1] += (dp[y - 1][x][0] + dp[y - 1][x][1]) % MOD;
			}

			// (y, x-1)이 장애물이 아니라면
			if (city_map[y][x - 1] == 0)
			{
				// (y, x)에 도달하는 수평 이동 경로의 수 갱신
				// 이 위치에는 수직, 수평이 모두 올 수 있음
				dp[y][x][0] += (dp[y][x - 1][0] + dp[y][x - 1][1]) % MOD;
			}

			// (y-1, x)가 정면이동 가능 장애물이라면
			if (city_map[y - 1][x] == 2)
			{
				// (y, x)에 도달하는 수직 이동 경로의 수 갱신
				// 이 위치에는 수직 이동만 올 수 있다
				dp[y][x][1] += (dp[y - 1][x][1]) % MOD;
			}

			// (y, x-1)이 정면이동 가능 장애물이라면
			if (city_map[y][x - 1] == 2)
			{
				// (y, x)에 도달하는 수평 이동 경로의 수 갱신
				// 이 위치에는 수평 이동만 올 수 있다
				dp[y][x][0] += (dp[y][x - 1][0]) % MOD;
			}
		}
	}

	// (m-1, n-1) 좌표에 도달하는 경로의 수 계산
	answer = (dp[m - 1][n - 1][0] + dp[m - 1][n - 1][1]) % MOD;
	return answer;
}