[백준 1937] 욕심쟁이 판다

문제 링크 => 1937번: 욕심쟁이 판다 (acmicpc.net)

1937번: 욕심쟁이 판다

 

다이나믹 프로그래밍 문제이다.

 

어떠한 지점 (x, y) 에서 존재하는 대나무를 먹고 다음 지점(nextX, nextY) 으로 이동할 때,

다음 지점(nextX, nextY) 에 존재하는 대나무의 갯수가 (x, y) 지점에 있던 대나무의 갯수보다 클 경우

다음 지점으로 이동하여 대나무를 먹는다.

이렇게 판다가 이동하면서 대나무를 야무지게 먹을 수 있는 최대 거리를 구해야 한다.

 

알 수 있는 사실은 다음과 같다.

이때, Dist(x, y) = 현재 지점에서 최대 대나무 갯수를 찾아가 끝까지 먹는데 걸리는 거리

 

① 대나무의 갯수가 가장 많이 있는 지점은 거리가 무조건 1이다.     

      무조건 다음 지점의 대나무 갯수가 더 커야 하는 성질을 이용한다면 성립함을 알 수 있다.

② 다음 지점으로 이동이 가능하다고 가정한다면(다음 지점에 대나무 갯수가 더 많은 경우)     

      Dist(x, y) = max(Dist(x, y), Dist(nextX, nextY) + 1) 이 성립한다.

③ 다음 지점으로 이동이 불가능하다고 가정한다면(다음 지점에 대나무 갯수가 같거나 적을 경우)     

      이 경우는 Skip 한다.

 

위 경우를 이용하여 대나무의 갯수가 가장 큰 지점 (x1, y1) 부터 갯수가 가장 작은 지점 (xn^2, yn^2) 까지

①, ②, ③ 에 대한 경우를 고려하여 코드를 짜면 다음과 같다. (Priority Queue를 이용함)

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue>
#include <algorithm>

using namespace std;

int n;
int Panda[501][501], dist[501][501];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
priority_queue<pair<int, pair<int, int>>> Panda_Queue;

int dfs(int x, int y) 
{
	int i, nextX, nextY;
	
	dist[x][y] = 1;
	for (i = 0; i < 4; i++) {
		nextX = x + dx[i], nextY = y + dy[i];
		if (nextX >= 1 && nextX <= n && nextY >= 1 && nextY <= n) {
			if (Panda[nextX][nextY] <= Panda[x][y])
				continue;
			if (dist[nextX][nextY] != -1)
				dist[x][y] = max(dist[x][y], dist[nextX][nextY] + 1);
			else
				dist[x][y] = max(dist[x][y], dfs(nextX, nextY));
		}
	}

	return dist[x][y];
}

void init() 
{
	int i, j;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			dist[i][j] = -1;
}

int solution() 
{
	int eat, x, y, max_eat;

	init();
	max_eat = 0;
	while (!Panda_Queue.empty()) {
		eat = Panda_Queue.top().first;
		x = Panda_Queue.top().second.first;
		y = Panda_Queue.top().second.second;
		Panda_Queue.pop();

		max_eat = max(max_eat, dfs(x, y));
	}

	return max_eat;
}

int main()
{
	int i, j;

	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			scanf("%d", &Panda[i][j]);
			Panda_Queue.push({ Panda[i][j], {i,j} });
		}
	}

	printf("%d", solution());

	return 0;
}