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

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

1937번: 욕심쟁이 판다

---

문제

 

---

접근 방법

 

판다는 기본적으로 현재 내 위치보다 대나무의 수가 적은곳에서 현재 위치로 이동이 된다.

주위에 현 위치 보다 대나무가 적은 곳이 없어서 현재 위치로 이동할 수 있는 경로가 없다면 그 곳으로 갈 수 있는 경로는 오직 그 위치에서 시작하는 경우 한 개이다.

따라서 위의 경우는 dp라는 array에 1이라는 값을 정해두고,

 

주위에 현 위치보다 대나무가 적은 곳이 있는 곳까지 갈 수 있는 경로는

max(현 위치보다 대나무 적은 주변 위치의 dp값) + 1 이 된다.

 

이러한 공식을 통해서 모든 대나무 숲의 경로의 최댓값을 구해주고, 그 값중에 가장 큰 값이 문제에서 원하는 판다가 이동 할 수 있는 칸의 수의 최댓값이 된다.

 

 

---

코드

#include<iostream>
#include<queue>
#include<string>
#include<algorithm>
using namespace std;
int n;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
int arr[501][501];
int dp[501][501];
int dpf(int x, int y) {
	if (dp[x][y] != -1)return dp[x][y]; //이미 구한 값이면 바로 dp값을 반환
	int m = 1;
	for (int i = 0; i < 4; i++) {
		int x2 = x + dx[i];
		int y2 = y + dy[i];
		if (x2 > 0 && y2 > 0 && x2 <= n && y2 <= n && arr[x2][y2] < arr[x][y]) {
			m = max(dpf(x2, y2) + 1, m);
		} //위의 조건을 만족 못 할때의 m값은 1이 된다.
	}
	dp[x][y] = m;
	return m;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	int m=1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) { 
		dp[i][j] = -1;
		cin >> arr[i][j]; }
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			m=max(m,dpf(i, j));
		}
	
	cout << m;
}

---

큰 어려움이 없는 DP문제였다.