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

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

1937번: 욕심쟁이 판다

백준 1937번 욕심쟁이 판다를 풀었다.

 

단순한 BFS/DFS 풀어보려 했는데 노드의 최대 개수인 250,000번을 수행해야 하므로 다른 방법을 사용해야 한다.

2차원 DP 배열과 DFS를 사용해서 풀었다.

DP[i][j] 의 값은 판다가 (i, j) 좌표에 놓여졌을 때 살 수 있는 최대 일 수 이다.

어느 좌표에 놓이든 하루는 살 수 있으므로 DFS실행 시 해당 좌표의 DP값은 1로 설정했다. 

DFS를 실행하면서 다음 좌표의 DP값 + 1 과 현재 좌표의 DP값을 비교해서 더 큰 것을 DP에 저장한다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <algorithm>
#pragma warning(disable:4996)

using namespace std;
#define INF 1234567890

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int map[500][500];
int dp[500][500];
int n;

int dfs(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 next_x = x + dx[i];
		int next_y = y + dy[i];
		if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < n
			&& map[x][y] < map[next_x][next_y]) {

			dp[x][y] = max(dp[x][y], dfs(next_x, next_y)+1);
		}
	}
	return dp[x][y];
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
		}
	}

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

	cout << max;
}