BOJ 2969 메뚜기

사용한 알고리즘

알고리즘 설명

정말 재미있는 문제이다. 메뚜기는 현재보다 높은 값의 꽃잎으로 점프 할 수 있다.
메뚜기는 현재 위치에서 8방의 위치로는 점프를 할 수 없으며, 상하좌우 인접한 열과 줄의 한 지점으로 점프할 수 있다.
DP를 사용하는데, 각 열과 줄에 대해서 최대 값을 저장한다. 하지만 여기서 특별한 점은 각 열과 줄에 4개의 최대 값을 저장한다는 점이다.
이유는 메뚜기가 각각 열과 줄에서 최대 3개의 지점에 대해서는 갈 수 없으므로, 최대 4개의 값을 저장하면 최대 DP값을 가지는 적어도 1개의 값을 얻을 수 있다.
OPT(here) = max(OPT(prev) + 1)의 형태로 현재 지점에서 인접한 열과 줄에서 OPT(prev)를 찾아서 OPT(here)를 업데이트 한다.
이때에 OPT(here)에 대해서 같은 꽃잎에서는 뛰지 못하도록 Queue에다 잠시 저장을 해 놓은 뒤에 꽃잎 수가 바뀔 때에 변경된 OPT 값들을 업데이트 한다.
이러한 OPT(here)값 중에 최대 값이 메뚜기가 뛸 수 있는 최대 꽃 수 이다.
시작점으로 부터 같은 꽃잎 수를 가지는 꽃은 모두 무시하고 시작보다 높은 꽃잎 수 중 오름차순 순서로 OPT값을 업데이트 해야 한다.

풀이

// baekjoon 2969 yechan
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
const int MAX_N=1501;
const int MIN_INF=-1e9;

struct Flower{
	int r, c;
	int petal;
	Flower():r(-1),c(-1),petal(0){}
	Flower(int r, int c, int petal):r(r),c(c),petal(petal){}
};

bool cmp(const Flower& a, const Flower& b) {
	return a.petal < b.petal;
}

struct PosAndDP{
	int x, value;
	PosAndDP():x(MIN_INF),value(MIN_INF){}
	PosAndDP(int x, int value):x(x),value(value){}
};

struct Pos2dAndDP{
	int r, c, value;
	Pos2dAndDP():r(-1),c(-1),value(MIN_INF){}
	Pos2dAndDP(int r, int c, int value):r(r),c(c),value(value){}
};

struct MemoPosAndDP{
	PosAndDP data[4];
	void update(int x, int value) {
		int i = 0;
		PosAndDP input = PosAndDP(x, value);
		for (i=0; i<4; i++) {
			if (data[i].value < input.value) {
				break;
			}
		}
		if (i == 4) return;
		PosAndDP target, tmp;
		target = input;
		while (i < 4) {
			tmp = data[i];
			data[i] = target;
			target = tmp;
			i++;
		}
	}
	int findMaximum(int x) {
		for (int i=0; i<4; i++) {
			if (abs(data[i].x - x) > 1) {
				return data[i].value;
			}
		}
		return 0;
	}
};

int N, R, C, board[MAX_N][MAX_N], ans;
Flower flowers[MAX_N*MAX_N];
MemoPosAndDP rows[MAX_N], cols[MAX_N];

int main() {
	scanf("%d", &N);
	scanf("%d%d", &R, &C);
	R--, C--;
	for (int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			scanf("%d", &board[i][j]);
			flowers[i*N+j]= Flower(i, j, board[i][j]);
		}
	}
	sort(flowers, flowers+N*N, cmp);

	queue<Pos2dAndDP> q;
	int prev_v;
	ans = 1;
	int ret = 1;
	int start = 0;
	for (int i=0; i<N*N; i++) {
		if (flowers[i].r == R && flowers[i].c == C) {
			rows[R].update(C, 1);
			cols[C].update(R, 1);
			prev_v=flowers[i].petal;
			while ((i < N*N) && (prev_v == flowers[i].petal)) {
				i++;
			}
			start = i;
			break;
		}
	}
	for (int i=start; i<N*N; i++) {
		if (prev_v != flowers[i].petal) {
			while (!q.empty()) {
				Pos2dAndDP tmp = q.front();
				rows[tmp.r].update(tmp.c, tmp.value);
				cols[tmp.c].update(tmp.r, tmp.value);
				q.pop();
			}
			prev_v = flowers[i].petal;
		}
		ret = MIN_INF;
		if (flowers[i].r - 1 >= 0)
			ret = max(ret, rows[flowers[i].r - 1].findMaximum(flowers[i].c) + 1);
		if (flowers[i].r + 1 < N)
			ret = max(ret, rows[flowers[i].r + 1].findMaximum(flowers[i].c) + 1);
		if (flowers[i].c - 1 >= 0)
			ret = max(ret, cols[flowers[i].c - 1].findMaximum(flowers[i].r) + 1);
		if (flowers[i].c + 1 >= 0)
			ret = max(ret, cols[flowers[i].c + 1].findMaximum(flowers[i].r) + 1);
		ans = max(ans, ret);
		q.push(Pos2dAndDP(flowers[i].r, flowers[i].c, ret));
	}
	printf("%d\n", ans);
	return 0;
}