[BAEKJOON] 1937번 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

문제조건

1. n x n 크기의 대나무숲
2. 어디든지 판다를 풀어놓을수 있다.
3. 판다는 대나무를 다먹으면 상, 하, 좌, 우 중 한지역으로 이동한다.
4. 이동하는 칸의 대나무가 원래있던 칸의 대나무 수보다 많아야 이동한다.
5. 가장 많이 이동하는 경우의 이동수는?

접근방법

 

문제를 보자마자 생각이 들었다.

'아 그냥 완전탐색돌려서 최댓값 갱신해서 찾자'

내가 좋아하는 DFS 알고리즘으로 모든 경우의 수를 계산했다.

 

#include <iostream>
#include <vector>

using namespace std;

int n, map[501][501], visited[501][501];
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };
int sum, res;

void dfs(int y, int x, int cnt) {
	sum = max(sum, cnt);
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= n || ny < 0 || nx >= n || nx < 0) continue;
		if (map[y][x] < map[ny][nx] && !visited[ny][nx]) {
			visited[ny][nx] = 1;
			dfs(ny, nx, cnt + 1);
			visited[ny][nx] = 0;
		}
	}
}

//판다 많이 이동시키기
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) cin >> map[i][j];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visited[i][j] = 1;
			dfs(i, j, 1);
			visited[i][j] = 0;
			res = max(res, sum);
		}
	}
	cout << res;
}

뭐야 너무 쉬운데,,?

 

라고 생각이들면 항상 틀리는 증후군이 있는것 같다 ㅎㅎㅎ

 

위 코드를 살펴보면 500 x 500 인 이중 for문을 돌고 있고, 이중 for문을 도는 것만해도 25만이라는 시간이 걸린다.

그런데 여기서 각 반복때마다 DFS를 수행하면 최악의 경우, 억단위가 넘어가버린다,,,

이제 해결을 하기 위해서 어떻게 하면 시간을 줄일 수 있을까 생각해봤다.

---

내가 짠 코드는 모든 경우의 수를 고려 한 것뿐만 아니라, 중복되는 경우의 수까지 계산하고 있다.

따라서 시간이 초과가 된 것인데, 이렇게 되면 DP를 활용한 memoization기법을 통해 이미 계산된 값들은 계산하는 과정없이 스킵하는 것이 필요하다.

 

 

memoization

 

동적계획법에서 이 방식은 top-bottom Approach를 적용한 하향식 접근방법이다.

필요한 값이 있으면, 앞에서 미리 계산해두었던 값들을 활용해서 구할 수 있기 때문에, 시간적으로 매우 이득을 볼 수 있는 장점을 가진다.

이 문제에 적용해보면, 4개의 방향으로 간 DFS로 계산한것에서 +1 한거랑  판다가 있는 좌표에서 이동하는 수랑 비교해서 큰값으로 갱신 시켜주면 된다!

소스코드

#include <iostream>
#include <vector>

using namespace std;

int n, map[501][501], dp[501][501];
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };
int res;

int dfs(int y, int x) {
	if (dp[y][x]) return dp[y][x];
	dp[y][x] = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= n || ny < 0 || nx >= n || nx < 0) continue;
		if (map[y][x] < map[ny][nx]) {
			dp[y][x] = max(dp[y][x], dfs(ny, nx) + 1);
		}
	}
	return dp[y][x];
}

//판다 많이 이동시키기
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) cin >> map[i][j];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			res = max(res, dfs(i, j));			
		}
	}
	cout << res;
}