Coding Test - cpp/DFS
[백준 1937: 욕심쟁이 판다] - C++
에드윈H
2021. 2. 15. 21:27
www.acmicpc.net/problem/1937
1937번: 욕심쟁이 판다
n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서
www.acmicpc.net
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
int n;
int map[501][501];
int dp[501][501];
int temp = -214000000;
int dir[4][2] = {
{-1,0}
,{0,1}
,{1,0}
,{0,-1}
};
int D(int _x, int _y)
{
if (dp[_x][_y] != 0)
{
return dp[_x][_y];
}
dp[_x][_y] = 1;
for (int i = 0; i < 4; i++)
{
int nextX = _x + dir[i][0];
int nextY = _y + dir[i][1];
if (nextX < 0 || nextY < 0 || n <= nextX || n <= nextY)
continue;
if (map[_x][_y] < map[nextX][nextY])
dp[_x][_y] = max(dp[_x][_y], D(nextX, nextY) + 1);
}
return dp[_x][_y];
}
int main() {
cin >> n;
int result = -214000000;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> map[i][j];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
temp = D(i, j);
if (result < temp)
{
result = temp;
}
}
}
cout << result << endl;
return 0;
}