백준 1937번: 욕심쟁이 판다 (C++)

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

1937번: 욕심쟁이 판다

 

 

판다가 너무 곱게 자랐는지 밥을 더 안주면 굶어 죽는 문제다. 딱보면 알겠지만 탐색문제이다. 브루트포스 문제를 풀듯이 모든 좌표에 대해 가능한 모든 경우의 수를 탐색하는 방법으로 풀어도 가능은 하겠지만, 그런 방법으로 풀면 분명 시간초과가 뜰것이다. 근데 조금 생각해보면 판다가 미쳐서 밥을 더주는 방향으로만 이동한다. 즉 그래프로 치환하여 생각하면, 사이클이 없을것이고 트리처럼 root에서 다른방향으로만 길이 있는 구조일것이다. 즉 어떤 특정 좌표값에서 시작해서 먹을수 있는 최대 바나나수를 알면, 그 특정값 좌표로 어떤 방향으로 들어와도 최대 바나나수는 바뀌지 않는다. 이점을 이용해서 브루트포스처럼 탐색을 하되, dp배열에 탐색한 좌표에는 값을 기록해놓아 나중에 재탐색하는 일을 방지하면 시간내에 충분이 문제가 풀릴것이다.

 

 

int board[501][501];
int dp[501][501];


int dfs(int x, int y){
	if(dp[x][y]!=0) return dp[x][y];

	dp[x][y] = 1;
	
	if(x-1>=0 && board[x][y] < board[x-1][y]){
		dp[x][y]= max(dp[x][y], 1+dfs(x-1,y));
	}
	if(x+1<n && board[x][y] < board[x+1][y]){
		dp[x][y]= max(dp[x][y], 1+dfs(x+1,y));
	}
	if(y-1>=0 && board[x][y] < board[x][y-1]){
		dp[x][y]= max(dp[x][y], 1+dfs(x,y-1));
	}
	if(y+1<n && board[x][y] < board[x][y+1]){
		dp[x][y]= max(dp[x][y], 1+dfs(x,y+1));
	}

	return dp[x][y];

}

위 깊이 탐색 함수를 보면

먼저 dp[x][y] 가 0이 아니면 그 값을 리턴하는데 이 과정이 미리 계산해놓은 값이 있는지 검사하는것이다. 만약 없으면 직접 깊이 탐색을 한 뒤에 dp[x][y]에 그 최대값을 저장하고 그 값을 리턴한다.

 

 

전체 코드는 아래와 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>



typedef long long ll;


using namespace std;
int n;
int board[501][501];
int dp[501][501];


int dfs(int x, int y){
	if(dp[x][y]!=0) return dp[x][y];

	dp[x][y] = 1;
	
	if(x-1>=0 && board[x][y] < board[x-1][y]){
		dp[x][y]= max(dp[x][y], 1+dfs(x-1,y));
	}
	if(x+1<n && board[x][y] < board[x+1][y]){
		dp[x][y]= max(dp[x][y], 1+dfs(x+1,y));
	}
	if(y-1>=0 && board[x][y] < board[x][y-1]){
		dp[x][y]= max(dp[x][y], 1+dfs(x,y-1));
	}
	if(y+1<n && board[x][y] < board[x][y+1]){
		dp[x][y]= max(dp[x][y], 1+dfs(x,y+1));
	}

	return dp[x][y];

}

int main(int argc, char** argv)
{	

	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

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

	int m = 0;
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++){
			m = max(m, dfs(i,j));
		}
	
	cout << m;
	
}