[BOJ/백준 1937/C++] 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

[문제 설명]

- N x N의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다.

- 이동하는 조건은 옮긴 지역의 대나무가 그 전 지역보다 많아야 한다.

- 판다가 이동할 수 있는 칸의 수의 최댓값을 출력하다.

 

[문제 조건]

- 숲의 크기 N ( 1 ≤ N ≤ 500 )가 첫째 줄에 주어진다.

- 둘째 줄부터 N+1번째 줄까지 대나무 숲의 정보가 주어진다.

- 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

- 시간 제한 : 2초

- 메모리 제한 : 256MB

 

[문제 풀이]

문제를 읽어보면 판다가 이동할 수 있는 경로의 길이의 최대값을 구하는게 주 목표이다. 따라서 DFS나 BFS를 이용하여 계산하면 풀리겠지라고 생각했지만 그리 간단한 문제는 아니였다.

 

왜냐하면 이 문제는 출발점이나 도착점이 따로 정해지지 않았다는 것이다. 그렇다는 것은 모든 위치에서 탐색을 돌려서 최대값을 구하면 되는데, 만약 숲의 크기가 최대 500x500일때 모든 위치에서 탐색을 돌리면 아마도 시간초과로 문제풀이를 실패할 것이다.

 

그렇다면 시간을 최대한 줄이기 위해서 이미 탐색을 한번 진행한 곳은 그 지점에서 갈 수 있는 경로의 길이의 최대값을 저장해놓고, 다른 지점에서 탐색을 했을때 이 지점을 방문하면 다시 탐색을 하지 않고 미리 저장해두었던 값을 리턴시켜줌으로서 시간을 줄일 수 있다. DFS와 DP가 합쳐진 문제라고 할 수 있다. (BFS로는 안해봤는데 아마 될 것 같다.)

 

간단하게 예를 들어보자.

3	4	5	6	7
2	13	14	15	8
1	12	11	10	9

 

위의 표와 같이 입력이 주어졌다고 가정해보자.

 

2번이 적인 곳에서 판다가 이동할 수 있는 경로의 최대는 2->3->4-> ..... ->13->14->15로 14칸이다. 그런 다음 1번이 적힌 곳에서 탐색을 시작한다고 생각해보자. 1번의 위쪽 방향으로 가면 2번이 적힌 칸이 있다. 그렇다면 굳이 2번에서 다시 탐색을 진행할 필요가 있는가? 어차피 탐색을 하면 또 14의 값이 나올텐데.

 

따라서 이 값을 따로 dp배열에 저장해놓고, 다른 칸에서 이 칸을 방문하려할때 미리 계산해둔 값을 리턴해주면 시간을 절약할 수 있다.

 

[소스 코드]

 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

using namespace std;

int n;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };
vector<vector<int>> mp;
vector<vector<bool>> ck;
vector<vector<int>> dp;

int dfs(int y, int x)
{
	ck[y][x] = true;

	int cur_value = dp[y][x];
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
		if (mp[ny][nx] <= mp[y][x]) continue;
		if (ck[ny][nx])
		{
			dp[y][x] = max(dp[y][x], cur_value + dp[ny][nx]);
			continue;
		}
		int tmp = dfs(ny, nx);
		tmp = tmp + cur_value;
		dp[y][x] = max(dp[y][x], tmp);
	}
	
	return dp[y][x];
	
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	mp.resize(n); dp.resize(n); ck.resize(n);
	for (int i = 0; i < n; i++)
	{
		mp[i].resize(n);
		ck[i].resize(n);
		dp[i].resize(n);
	}
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { dp[i][j] = 1; }

	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { cin >> mp[i][j]; }

	int max_ans = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (ck[i][j]) continue;
			max_ans = max(max_ans,dfs(i, j));
		}
	}
	cout << max_ans;
}

굳