[ 프로그래머스 ] 보행자 천국 (C++)

프로그래머스

 

난이도 :  Level 3 
알고리즘 유형 : DP 
풀이 시간 : 1시간 8분 

문제 풀이 

보행자 중심의 경로 탐색 알고리즘을 구현하려고 한다. 

- `city_map[i][j] == 0` 인 경우에는 자동차가 자유롭게 지나갈 수 있다.

- `city_map[i][j] == 1` 인 경우에는 자동차의 통행이 금지된다.

- `city_map[i][j] == 2` 인 경우에는 가던 방향으로만 이동할 수 있다.

자동차는 오른쪽 또는 아래 방향으로만 이동이 가능하다. 가능한 이동 경로의 개수를 구하자.

 

해당 문제는 가능한 경로의 총 개수를 구하는 것이 중점이고, 입력 grid의 크기가 $1 ≤ m, n ≤ 500$이기 때문에, 단순한 탐색으로는 시간초과가 날 것이다. 

 

따라서, 이 문제는 가능한 경우를 누적해주는 DP를 활용하여 풀어나가면 된다. DFS와 DP를 활용한 Top - Down 방식으로 문제를 풀어나갔다. 

 

먼저, DP 테이블 초기화의 경우에는 전체 grid의 크기와 방향 별로 이동 경로의 개수를 확인해야 하기 때문에 3차원으로 표현해주었다. (dp[501][501][2])

 

재귀 함수의 반환 조건은 다음과 같이 설정하였다. 

1. 만약 오른쪽 아래 도착 지점(m - 1, n - 1)에 무사히 도착했다면, 가능한 경우임을 나타내기 위해 1 return

2. 만약 `city_map[i][j] == 1`인 경우에는 가지 못하므로 0 return

3. 만약 메모이제이션으로 인해 해당 정점에서의 경우의 수가 모두 계산되었다면, 해당 메모값 return

 

마지막으로, 각각의 city_map 정점의 조건에 따라서 이동 경로 역시 다르게 설정해주었다.

 

처음에 dfs를 호출하는 부분을 확인해보면, 초기 d 정보를 0으로 주었는데, 이는 1로 주어도 상관이 없다. 그 이유는 어차피 출발 정점인 `(0, 0)`은 어떤 방향에 있든지간에 계산에 영향을 주지 않기 때문이다.

 

코드

/*
도심의 일부 구역은 자동차 통행이 금지, 일부 교차로에서는 좌우회전 금지
1: 자동차 통행 금지
2: 직진만 가능
도로 상태가 입력으로 주어졌을 때, 이동가능한 전체 가능 경로 수를 출력하자
가능한 경로 수를 20170805로 나눈 나머지값을 출력

풀이 : DFS + DP
메모이제이션 방식을 사용한다.
경로 이동은 동일하게 활용하기

grid[r][c] 가 2인 경우는 따로 조건문 걸어주기
*/


#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int MOD = 20170805;

int N, M;
int grid[501][501] = { 0, };
int dp[501][501][2];

int dr[2] = { 0, 1 };
int dc[2] = { 1, 0 };

bool isValid(int r, int c) {
	return 0 <= r && r < N && 0 <= c && c < M;
}

int dfs(int r, int c, int d) {
	if (r == N - 1 && c == M - 1)
		return 1;
	if (grid[r][c] == 1)
		return 0;
	if (dp[r][c][d] != -1)
		return dp[r][c][d];
	int nr, nc;
	int tmp = 0;
	// 직진만 가능한 경우
	if (grid[r][c] == 2) {
		nr = r + dr[d], nc = c + dc[d];
		if (isValid(nr, nc)) {
			tmp += (dfs(nr, nc, d) % MOD);
		}
	}
	else {
		for (int nd = 0; nd < 2; nd++) {
			nr = r + dr[nd], nc = c + dc[nd];
			if (isValid(nr, nc)) {
				tmp += (dfs(nr, nc, nd) % MOD);
			}
		}
	}
	dp[r][c][d] = tmp % MOD;
	// cout << r << ' ' << c << ' ' << dp[r][c][d]<< '\n';
	return dp[r][c][d];
}


// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
	int answer = 0;
	N = m, M = n;
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++)
			grid[i][j] = city_map[i][j];
	}

	answer = dfs(0, 0, 0);

	return answer;
}

배운 점 

이후 bottom-up을 활용한 코드를 실행시켜 본 결과 실행 시간이 약 2배 정도 빠른 것을 확인할 수 있었다.

(top-down : 52ms, bottom-up : 21ms)

 

이를 통해 배열의 사이즈가 큰 경우에는 bottom - up 이 더 효율적일 것이라는 생각을 하게 되었고, 같은 dp여도 상황에 맞게 적절한 방법을 사용해야 함을 알 수 있었다.