[BOJ-1937] 욕심쟁이 판다 (C++)

백준 1937 욕심쟁이 판다

 

1937번: 욕심쟁이 판다

문제 설명

 

 - nxn 크기의 대나무 숲이 있다.

 

 - 욕심쟁이 판다는 대나무 숲에서 대나무를 먹는다.

 

 - 판다는 현재 위치에서 대나무를 다 먹은 경우 상, 하, 좌, 우 한 곳으로 이동한다.

   이때 현재 위치의 대나무수 보다 많은 수의 대나무가 있는 위치로 이동한다.

   

 - 판다를 어느 위치에도 놓을 수 있다.

 

 - 판다가 최대한 오래 살 수 있는 일수를 구하라.

---

 

입력 값

 

 - 첫째 줄에 대나무 숲의 크기 n( 1 <= n <= 500) 이 주어진다.

 

 - 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다.

 

 - 대나무 숲의 정보는 공백 사이러 두고 각 지역의 대나무의 양이 정수 값으로 주어진다.

   대나무의 양은 100만 이하의 자연수이다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 간단하게 생각하면, 해당 위치에서 팬더가 살 수 있는 모든 경우의 수를 확인한다.

 

 - 해당 방법은 nxn의 대나무 숲에서 모든 방법을 찾는 방법은 모든 경로를 살펴보아야 하기 때문에 $n^2$의 경우의 수가 있다.

 

 - 즉, 시간 복잡도는 O($n^4)가 된다. 즉, $500^4$ = 625억이 되기 때문에 불가능하다.

 

 - 문제를 다시 살펴보면, 해당 위치에서 팬더가 오래 살 수 있는 일수는 정해져 있다.

   그렇기 때문에 해당 위치에서 오래 살 수 있는 일 수를 한 번 계산하면, 다시 계산할 필요가 없다는 것이다.

 

 - 즉, 이 문제는 DFS + 메모이제이션을 이용하여 해결할 수 있다.

 

 - 방법을 정리하자면

    1. nxn 위치를 모두 살펴보면서 해당 위치에서 dfs를 시작한다.

    2. 해당 위치에서 오래 살 수 있는 최대 일수를 구하여 저장한다.

    3. 해당 위치를 이미 계산했다면 그 값을 사용하고, 아니면 dfs를 계속 실행한다.

 

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

int n;

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

// 해당 위치 대나무 수
int boards[501][501];

// 해당 위치에서 시작했을 때 최다 대나무 개수
int visited[501][501];


int dfs(int y, int x) {

	if (visited[y][x] != 0) {
		return visited[y][x];
	}

	int nowCost = boards[y][x];
	visited[y][x] = 1;

	for (int d = 0; d < 4; d++) {
		int ny = y + dy[d];
		int nx = x + dx[d];
		
		if (ny < 0 || nx < 0 || ny >= n || nx >= n || nowCost >= boards[ny][nx]) {
			continue;
		}
		
		visited[y][x] = max(visited[y][x], 1 + dfs(ny, nx));

	}

	return visited[y][x];

}

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

	cin >> n;

	int result = 0;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int c;
			cin >> c;
			boards[i][j] = c;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visited[i][j] != 0) {
				continue;
			}

			result = max(result, dfs(i, j));
		}
	}

	cout << result << endl;


	return 0;
}