백준 1937 욕심쟁이 판다

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 시간 제한이 있기 때문에 일반적으로 모든 좌표에서 생존 가능일을 구하게 되면 시간 초과가 납니다.

 

제가 아직 dp문제에 익숙하지 않아서 푸는데 고생을 많이 하였습니다 ㅠㅠ.. 기본적으로 mov라는 이동 함수를 만들고 이를 재귀적으로 탐색을 하는데 이 과정에서 이미 갱신이 되어있는 좌표는 보지않고 넘어가도 되는것이 포인트 입니다.

 

또한 한 좌표에서 여러 방향으로 이동이 가능 할 경우 각 방향으로 들어가서 끝까지 간다음 그때의 생존가능일 들을  비교하여 더큰 값이 남도록 해주면 됩니다. 

 

예시를 들자면 어떤 좌표 x,y에서 5칸이 이동 가능하다면     1 -> 1 -> 1 -> 1-> 1  이렇게 이동한 다음 차례대로 +1 씩리턴이 되어 2 3 4 5가 각각 저장되어 각각의 좌표에서 5 4 3 2 1 이라는 생존가능일이 저장이 됩니다. 다른좌표에서 이미 갱신된 값으로 이동을 하면 그 값을 리턴하여 바로 +를 해주게 됩니다. 예를 들면 3아래의 좌표에서 2라는 값을 가진 채로 3이 저장된 좌표로가면 3아래의 좌표는 5라는 값으로 갱신이 됩니다.(2일생존 한채로 3일 생존이 +)

 

설명이 좀 횡설수설 한 것 같은데 나머지는 코드를 봐주시면 감사하겠습니다..

 

#include <iostream>

using namespace std;

int tree[501][501]; //대나무 숲 
int date[501][501]; //좌표에서 생존 가능일 
 
int xpos[] = {1,0,-1,0}; //좌우 
int ypos[] = {0,1,0,-1}; //상하 
int maxday;

int mov(int x, int y) {
	int nextx;
	int nexty;
	if(date[x][y] == 0)  
		date[x][y] = 1;
	else //생존가능일이 이미 갱신되어 있다면 return 
		return date[x][y];
	
	for(int i = 0; i < 4; i++) { //상하좌우 반복 
		nextx = x + xpos[i];
		nexty = y + ypos[i];
		if(nextx < 0 || nextx >500 || nexty < 0 || nexty > 500) //인덱스 벗어날경우 continue 
			continue;
			
		if(tree[x][y] < tree[nextx][nexty] ) { //이동할수 있는경우 
			int nm = mov(nextx, nexty) +1;
			if(date[x][y] < nm) //기존 날짜보다 이동해서 얻은 생존가능일이 더 크다면 값을 바꿈 
				date[x][y] = nm;
			}
		}
	
	return date[x][y];
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n;
	int result;
	cin >> n;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			cin >> tree[i][j];
	
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			if(date[i][j] == 0) { //생존가능일이 0이라면 탐색 시작 
				result = mov(i, j);
				if(maxday < result)
					maxday = result;
			}
	
	cout << maxday;
	return 0;
}