[백준 BOJ 1937 glod3 - 욕심쟁이 판다] DFS(?) , DP C++

백준 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

 

어떤 칸에서 출발하여 계속 대나무가 더 많은 쪽으로만 이동할 때, 최대로 움직일 수 있는 칸의 개수를 구하는 문제이다.

 

처음에 단순 DFS인줄 알고 이중 for문을 돌며 모든 칸에 대해 dfs를 돌려 최대 칸의 개수를 구했더니 시간초과가 났다.

 

이 문제는 재귀로 dp를 구현해서 풀면 되는 문제였다. 

풀이 해법은 https://yabmoons.tistory.com/154 블로그 글을 참고하였다!

 

핵심 아이디어는

dp[x][y] 에는 이 칸에서 판다가 최대로 살 수 있는 날을 저장하는 것이다.

모든 칸은 기본적으로 최소 dp배열에 1을 넣어준다. 최소 그 칸에서는 대나무를 먹을 수 있기 때문이다.

3	6
1	7

예를 들어 (1,1) 위치에서는 3->6->7 으로 총 세칸이다. dp[1][1] = 3

 

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <string>
#include <string.h>
#include <iostream>
#include <map>

using namespace std;

int N;
int tree[501][501];
int dp[501][501];

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,1,-1 };

bool range(int x, int y) {
	if (x >= 1 && y >= 1 && x <= N && y <= N)
		return true;
	return false;
}
int DP(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 nx = x + dx[i];
		int ny = y + dy[i];
		if (range(nx, ny) && tree[x][y] < tree[nx][ny]) {
			dp[x][y] = max(dp[x][y], DP(nx, ny) + 1);
		}
	}
	return dp[x][y];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> tree[i][j];
		}
	}
	int dab = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			dab = max(dab, DP(i,j));
		}
	}
	cout << dab;
}

 

재귀로 dp를 구현하는 아이디어를 떠올리는 것과 직접 구현하는게 아직은 어렵게 느껴진다..

어려운 dp문제를 더 풀어봐야 할 것 같다.