[C언어 / 백준 - 1937] 욕심쟁이 판다 (DFS / DP)

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

1937번: 욕심쟁이 판다

문제

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-)

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

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

출력

첫째 줄에는 판다가 최대한 살 수 있는 일수(K)를 출력한다.

 

 

갈 수 있는 경로를 파악하면서 가장 깊게 들어갈 때을때의 깊이를 알아내야하는 DFS문제이다.

처음에는 500*500이기에 모든 범위를 DFS로 훑고 그 중 가장 큰 값을 출력하는 식으로 문제를 풀었는데 당연히 시간초과가 났다...

아직 시간복잡도를 계산하기에 어려움이 있다. 질문검색을 통해 힌트를 얻었고, 메모제이션 기법을 통해 이미 알고 있는 위치는 값만 돌려받아 더하는 형식으로 필요없는 연산은 하지 않는 형식으로 시간을 줄여야한다는 걸 알 수 있었다.

 

!!메모제이션 기법을 통해 이미 깊이를 알고 있는 위치는 값만 돌려받고 더하는 형식으로 시간을 줄이자!!

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>
#define MAX_SIZE 501
#define MAX(a,b) a<b?b:a

int Graph[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE][MAX_SIZE];

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

void Input_Data() {
	scanf("%d", &N);
	for (int x = 0; x < N; x++){
		for (int y = 0; y < N; y++) {
			visited[x][y] = -1;
			scanf("%d", &Graph[x][y]);
		}
	}
}

int DFS(int x_, int y_) {
	if (visited[x_][y_] != -1) {
		return visited[x_][y_];
	}
	visited[x_][y_] = 1;

	for (int i = 0; i < 4; i++) {
		int nextX = dx[i] + x_;
		int nextY = dy[i] + y_;

		if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N) {
			if (Graph[x_][y_] < Graph[nextX][nextY]) {
				int day = 1;
				day += DFS(nextX, nextY);
				visited[x_][y_] = MAX(visited[x_][y_], day);
				if (visited[x_][y_] > k) k = visited[x_][y_];
			}
		}
	}
	return visited[x_][y_];
}

void Solve() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j] == -1)
				DFS(i, j);
		}
	}
}

int main() {
	Input_Data();
	Solve();
	printf("%d\n", k);

	return 0;
}