[백준 1937] 욕심쟁이 판다 (C++)

문제 링크: www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

1. 주의할 점

- 메모아이징 기법을 이용한다

- 값을 저장해서 사용하는 형태로 한다

 

2. 구현

- 모든 수를 입력 받고,  Check[][] 배열에는 현재 지점에서 시작하여 살 수 있는 최대 일수를 저장한다

- 만약 Check[][] 값이 0이라면 DFS()를 수행한다

- DFS(y,x) 함수에는 이미 해당 Check[y][x] 값이 양수라면 해당 값을 반환한다. 0이라면, 현재 위치를 기준으로 4방 탐색을 통해 대나무가 더 많은 쪽으로 이동하여 값을 갱신할 수 있도록 한다

- Int 반환형을 통해 이동했던 쪽으로 갈 수 있는 최대값을 계속해서 Return 받으며, Return 받은 최대값+1을 현재 위치의 Check[][] 배열에 저장한다

- Check[][] 배열중에서 가장 큰 값을 출력한다

 

#include <iostream>
#include <algorithm>
using namespace std;
int arr[500][500], check[500][500], num;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

int dfs(int y, int x) {
	int &ret = check[y][x];
	if (check[y][x]) return ret;
	int temp = 0;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && ny >= 0 && nx < num && ny<num && arr[ny][nx]>arr[y][x]) {
			temp = max(temp, dfs(ny, nx));
		}
	}
	ret = temp + 1;
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> num;
	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++)
			cin >> arr[i][j];
	int result = 0;
	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++)
			if (check[i][j] == 0) 
				dfs(i, j);				
	for (int i = 0; i < num; i++) 
		for (int j = 0; j < num; j++) 
			result = max(result, check[i][j]);	
	cout << result;
	return 0;
}