[백준] 1937 욕심쟁이 판다

1937번: 욕심쟁이 판다

문제 확인

 

dfs 커팅, 완전 탐색으로 풀 수 있지만 500x500 이므로 크기가 커서 효율성이 떨어지기 때문에 dfs, dp로 풀어야 합니다.

 

풀이

 

판다는 전 지역보다 옮긴 지역이 더 많은 대나무가 있어야 하므로 다음식을 항상 만족합니다.

ary[ path[i][x] ][ path[i][y] ] < ary[ path[i + 1][x] ][ path[i + 1][y] ]

따라서 dfs 탐색 도중 왔던 길을 다시 갈 수 없기 때문에 visited를 사용하지 않아도 됩니다. 

 

dp[x][y] : 현재 위치에서 갈 수 있는 최대 depth로 두고 문제를 풉니다.

배열 범위를 나가지 않는 선에서 다음 식을 통해 dp를 완성할 수 있습니다.

for( 상, 하, 좌, 우)
	if(ary[x][y] < ary[next x][next y])
    	dp[x][y] = max(dp[x][y], dfs(next x, next y);
dp[x][y]++;

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, ary[500][500], dp[500][500];
int dx[] = { 0, 0, 1, -1 },
dy[] = { 1, -1, 0, 0 };
 
int dfs(int x, int y) {
    int &cur = dp[x][y];
    if (cur) return cur;
 
    for (int d = 0; d < 4; d++) {
        if (x + dx[d] < 0 || n <= x + dx[d] || y + dy[d] < 0 || n <= y + dy[d]) continue;
        if (ary[x][y] < ary[x + dx[d]][y + dy[d]])
            cur = max(cur, dfs(x + dx[d], y + dy[d]));
    }
    return ++cur;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> ary[i][j];
    int mx = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (!dp[i][j])
                mx = max(mx, dfs(i, j));
    cout << mx;
}