[baekjoon 1937] 욕심쟁이 판다 (DFS+DP) (C++)

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

판다는 상하좌우 움직일 수 있으며, 자기가 먹은 대나무보다 더 많은 대나무가 있어야 움직인다.

만약 네 방향 모두 현재 먹은 대나무보다 적으면 움직이지 않고 죽어버린다고 한다..

즉, 현재보다 더 큰 수가 있어야 움직이며, 그 경로들 중 최장거리를 출력하면 된다.

 

따라서 DFS를 하되, 만약에 모든 칸에서 DFS를 돌려서 장거리를 계산한다고 하면 매번 n^2 만큼에 그걸 또 n^2번 돌리니 시간 복잡도가 터져버릴 것이라고 생각했다.

즉, DP를 이용해서 이미 방문한 경로에 대한 값을 저장해서 탐색 횟수를 줄여야 한다.

 

DP 배열의 의미는 그 점에서의 최장 경로를 저장해둔 것이다.

그렇게 되면, 다른 점에서 탐색을 하다가 이미 방문한 점을 탐색하게 되면 이미 그 점에서 탐색했을 경우에 나올 수 있는 최장 경로가 저장되어 있기 때문에 또 같은 탐색을 할 필요가 없게 되는 것이다.

 

ex) a점은 탐색의 결과 a점에서의 최장 경로가 (a 5 -> b 8 -> c 10)으로 length 3이 저장되어 있다.)

그 이후 어떤 점 d 2에서 a를 방문했을 경우 또 (d 2-> a 5-> b 8-> c 10) 탐색을 할 필요가 없이 3을 리턴 받으면 된다.

우리는 a점을 가면 어떤 경로가 최장 경로로 탐색이 될지 이미 해봐서 알기 때문이다..

 

따라서 DP 배열에 경로 값이 저장되어 있으면 그 값을 가져오면서 네 방향 중 가장 긴 거리를 저장해주면 된다.

 

#include <iostream>

using namespace std;

int n, arr[501][501], dp[501][501];
int xmove[4] = { 1, -1, 0, 0 }, ymove[4] = { 0,0,1,-1 };

int DFS(int startx, int starty) {
	if (dp[startx][starty] != -1)
		return dp[startx][starty]+1;

	else {
		dp[startx][starty] = 1;

		for (int i = 0; i < 4; i++) {
			int x = startx + xmove[i];
			int y = starty + ymove[i];
			if (x >= 0 && x < n && y >= 0 && y < n) {
				if (arr[x][y] > arr[startx][starty]) {
					dp[startx][starty] = max(dp[startx][starty], DFS(x, y));
				}
			}
		}
		return dp[startx][starty]+1;
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			dp[i][j] = -1;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
				DFS(i, j);
		}
	}

	int mx = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			mx = max(mx, dp[i][j]);
		}
	}
	cout << mx;
}