[프로그래머스] 보행자 천국

링크

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

코딩테스트 연습 - 보행자 천국 | 프로그래머스

풀이

도시의 도로 상태가 입력으로 주어졌을 때, 왼쪽 위의 출발점에서 오른쪽 아래 도착점까지 자동차로 이동 가능한 전체 가능한 경로 수를 출력하는 프로그램을 작성하는 문제이다.

 

문제를 봤을때 백준의 내리막 길과 상당히 유사한 문제라고 생각하였는데

혹시 보행자 천국문제를 못푸신 분이라면 내리막 길을 한번 풀어보고 오시는것도 좋을것 같습니다.

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

 

문제로 돌아와서 문제를 풀면서 가장 많이 고민 한것이

직진만 할수 있는 구간에 도착했을때 내가 왼쪽에서 왔는지 위에서 왔는지를 확인하는것을 어떻게 가지고 와야되는가 였는데. 

 

3차원 dp를 이용하여 고민을 해결 할 수 있었다.

dp[어디에서 왔는가(위쪽, 왼쪽)][x][y] 라는 dp배열을 만들 수 있었고

 

이때 출발점은 오른쪽 , 아래 어디든 갈수 있는 경우이기 때문에

출발점에서 오른쪽으로 출발 하였을때와, 아래쪽으로 출발 하였을때 각각 2개로 나누어 dfs탐색을 시작 하였고,

 

dp배열을 모두 -1로 초기화 하여 다음 지점의 방문 체크를 하였고, 방문 하지 않았다면 계속 dfs탐색을 진행하고

방문 하였다면 방문한 지점을 또 다시 갈 필요 없기 때문에 방문한 지점의 값을 가지고와 더해 주었다.

 

이렇게 오른쪽과 아래쪽의 dfs탐색을 모두 마치고 두 값을 더해주어 결과를 찾아 낼 수 있습니다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>

#define SIZE 510
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

int MOD = 20170805;

int dx[4] = { 0,1 };
int dy[4] = { 1,0 };

int dp[2][SIZE][SIZE];

//이때 stop은 내가 현재 지점에 왔을때 어떤 방향에서 왔는지 알려주는 변수
//0이면 왼쪽에서 오른쪽으로, 1이면 위쪽에서 아래쪽으로 이동
int dfs(int h_x, int h_y, int m, int n , int stop, vector<vector<int>> &city_map) {
	if (h_x == m - 1 && h_y == n - 1)
		return dp[stop][h_x][h_y] = 1;

	if (dp[stop][h_x][h_y] != -1)
		return dp[stop][h_x][h_y] % MOD;

	dp[stop][h_x][h_y] = 0;

	for (int d = 0; d < 2; d++) {
		int n_x = h_x + dx[d];
		int n_y = h_y + dy[d];

		if (n_x < 0 || n_x >= m || n_x < 0 || n_y >= n)
			continue;
		
        //0이면 오른쪽 아래쪽 아무곳이나 갈수 있음
		if (city_map[h_x][h_y] == 0) {
			dp[stop][h_x][h_y] = (dp[stop][h_x][h_y] + dfs(n_x, n_y, m, n, d, city_map)) % MOD;
		}
		if (city_map[h_x][h_y] == 1) {
			continue;
		}

		if (city_map[h_x][h_y] == 2) {
        	//이전에 왔던 방향으로 직진해야 하기 때문에 stop와 d가 같아야 직진함
			if (stop == d) {
				dp[stop][h_x][h_y] = (dp[stop][h_x][h_y] + dfs(n_x, n_y, m, n, stop, city_map)) %MOD;
			}
		}
	}
	return dp[stop][h_x][h_y] % MOD;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
	memset(dp, -1, sizeof(dp));

	//출발점에서 오른쪽으로 이동
	int right = dfs(0, 1, m, n, 0, city_map);
    //출발점에서 아래쪽으로 이동
	int down = dfs(1, 0, m, n, 1, city_map);

	return (right+ down) % MOD;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int m, n; cin >> m >> n;

	vector<vector<int>> city_map;

	for (int i = 0; i < m; i++) {
		vector<int> city;
		for (int j = 0; j < n; j++) {
			int road; cin >> road;
			city.push_back(road);
		}
		city_map.push_back(city);
	}

	cout << solution(m, n, city_map);
}