[백준] 1937. 욕심쟁이 판다 + 복습

문제

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

 

골드 3 DP+DFS문제입니다.

 

DFS만 사용하는경우 같은 지점에서 수없이 많이 다시 DFS를 수행합니다. 따라서 중복을 막아야 합니다.

한 지점에서 한번DFS탐색을 한 경우, 그 지점에서의 방문가능 경로의 길이는 다시 업데이트될 필요가 없습니다. 따라서 메모라이제이션을 통해 값을 저장하면, 다른지점에서 이미 방문한 지점을 방문할 경우 더이상 탐색을 하지 않아도 됩니다.

 

#include<bits/stdc++.h>
using namespace std;
int n, m;
int mp[501][501];
int visited[501][501];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int ans = -1;
int dfs(int y, int x) {

    if (visited[y][x] != -1)  //이미방문한좌표는 값이 바뀌지 않습니다.
        return visited[y][x];

    visited[y][x] = 1;//방문한경우 해당좌표의 개수 1을 저장합니다.
    int k = 0;
    for (int i = 0; i < 4; i++) {
        if (y + dy[i] >= 0 && y + dy[i] < n && x + dx[i] >= 0 && x + dx[i] < n) {
            if (mp[y][x] < mp[y + dy[i]][x + dx[i]]) {
                k = max((dfs(y + dy[i], x + dx[i])), k); //k는 그 해당지점에서 갈 수있는 최대경로 길이
            }
        }
    }
    visited[y][x] += k;
    return visited[y][x]; 
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(mp, 0, sizeof(mp));
    memset(visited, -1, sizeof(visited));

    int x;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> x;
            mp[i][j] = x;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans, dfs(i, j));
        }
    }
    cout << ans;
}

============================================================================================

 

2023-02-13

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };

int N, mp[501][501], v[501][501], ans = -1;

int dfs(int y, int x) {
	if (v[y][x])return v[y][x];
	rep(i, 4) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny>=0 && ny<N && nx>=0 && nx<N && mp[y][x] < mp[ny][nx])
			v[y][x] = max(v[y][x], dfs(ny, nx)+1);
	}
	v[y][x] = v[y][x] ? v[y][x] : 1;
	ans = max(ans, v[y][x]);
	return v[y][x];
}
int main() {
	FAST;
	cin >> N;
	rep(i, N)rep(j, N)cin >> mp[i][j];
	rep(i, N)rep(j, N)if (!v[i][j])dfs(i, j);
	cout << ans;
}

DP를 사용합니다 한번방문햇으면 또다시 방문할 필요가 없기때문입니다!!

메모제이션을 사용합니다.