[백준 21611] 마법사 상어와 블리자드

중랑천 입수하기엔 ~~~ 아직 일러~~~~ 힘내 내 머가리 ~~~~

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

21611번: 마법사 상어와 블리자드

#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
int N, M;
int board[50][50];
int sx, sy;

int tmp[50][50];
int ans[4];

struct _st
{
	int x, y;
};
int S[50][50];
_st S_lookup[2500];	// 죽어야겠다


struct _ct
{
	int d, s;
};

_ct CMD[100 + 2];

struct _qt
{
	int num;
	int x, y;
};

// 좌 하 우 상
int dir_x[4] = { 0, 1, 0, -1 };
int dir_y[4] = { -1, 0, 1, 0 };

void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &board[i][j]);
		}
	}
	for (int m = 0; m < M; m++) {
		scanf("%d %d", &CMD[m].d, &CMD[m].s);
	}
	sx = N / 2; 
	sy = N / 2;
}

void make_snail()
{
	int num = 1;
	int x = sx;
	int y = sy;
	int p = 0;

	for (int n = 1; n <= N - 1; n++) {
		for (int i = 0; i < 3; i++) {
			if (n != N - 1 && i == 2) break;
			for (int j = 1; j <= n; j++) {
				int nx = x + dir_x[p];
				int ny = y + dir_y[p];

				if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
				S[nx][ny] = num;
				S_lookup[num] = { nx, ny };
				num++;
				x = nx; y = ny;
			}
			p = (p + 1) % 4;
		}
	}
}


void throw_ice(int m)
{
	//  1↑, 2↓, 3←, 4→
	int Tdir_x[5] = { 0, -1, 1, 0, 0 };
	int Tdir_y[5] = { 0, 0, 0, -1, 1 };

	int dir = CMD[m].d;
	int speed = CMD[m].s;

	for (int s = 1; s <= speed; s++) {
		int nx = sx + (s * Tdir_x[dir]);
		int ny = sy + (s * Tdir_y[dir]);
		if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) return;
		board[nx][ny] = 0;
	}
}


void re_arrange()
{
	std::queue<int> AQ;	// arrange queue
	int x = sx;
	int y = sy;
	int p = 0;

	// 구슬 빼기 
	for (int n = 1; n <= N - 1; n++) {
		for (int i = 0; i < 3; i++) {
			if (n != N - 1 && i == 2) break;
			for (int j = 1; j <= n; j++) {
				int nx = x + dir_x[p];
				int ny = y + dir_y[p];

				if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
				if (board[nx][ny] == 0) {
					x = nx, y = ny;
					continue;
				}
				AQ.push(board[nx][ny]);
				x = nx; y = ny;
			}
			p = (p + 1) % 4;
		}
	}

	// 구슬 넣기 
	memset(board, 0, sizeof(board));
	int num = 1;

	while (!AQ.empty()) {
		int data = AQ.front();
		AQ.pop();

		int nx = S_lookup[num].x;
		int ny = S_lookup[num].y;
		board[nx][ny] = data;
		num++;
		if (num == N * N) break;
	}
}


bool blow_up()
{
	std::queue<_qt> BQ;	// blowup queue
	int x = sx;
	int y = sy;
	int p = 0;
	bool bomb = false;
	BQ.push({ board[x][y], x, y });

	for (int n = 1; n <= N - 1; n++) {
		for (int i = 0; i < 3; i++) {
			if (n != N - 1 && i == 2) break;
			for (int j = 1; j <= n; j++) {
				int nx = x + dir_x[p];
				int ny = y + dir_y[p];

				if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
				if (BQ.front().num != board[nx][ny]) {
					if (BQ.front().num == 0) {
						BQ = {};
						BQ.push({ board[nx][ny], nx, ny });
					}
					else {
						if (BQ.size() >= 4) {
							bomb = true;
							ans[BQ.front().num] += BQ.size();
							while (!BQ.empty()) {
								int bx = BQ.front().x;
								int by = BQ.front().y;
								BQ.pop();
								board[bx][by] = 0;
							}
						}
						else BQ = {};
						BQ.push({ board[nx][ny], nx, ny });
					}
				}
				else if (BQ.front().num == board[nx][ny] && board[nx][ny] != 0) BQ.push({ board[nx][ny], nx, ny });
				x = nx; y = ny;
			}
			p = (p + 1) % 4;
		}
	}
	return bomb;
}


void trans_ball()
{
	memset(tmp, 0, sizeof(tmp));
	std::queue<int> TQ;	// trans_ball queue
	std::queue<std::pair<int, int>> PTQ;	// trans_ball queue for tmp

	int x = sx;
	int y = sy;
	int p = 0;
	TQ.push(board[x][y]);

	// 정보 벡터에 넣기 
	for (int n = 1; n <= N - 1; n++) {
		for (int i = 0; i < 3; i++) {
			if (n != N - 1 && i == 2) break;
			for (int j = 1; j <= n; j++) {
				int nx = x + dir_x[p];
				int ny = y + dir_y[p];

				if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
				if (TQ.front() != board[nx][ny]) {
					if (TQ.front() == 0) {
						TQ = {};
						TQ.push(board[nx][ny]);
					}
					else {
						PTQ.push({ TQ.size(), TQ.front() });
						TQ = {};
						TQ.push(board[nx][ny]);
					}
				}
				else if (TQ.front() == board[nx][ny] && board[nx][ny] != 0) TQ.push(board[nx][ny]);
				x = nx; y = ny;
			}
			p = (p + 1) % 4;
		}
	}

	// 꺼내기
	int num = 1;
	int tx = sx;
	int ty = sy;
	while(!PTQ.empty()) {
		int ball_sz = PTQ.front().first;
		int ball_num = PTQ.front().second;
		PTQ.pop();
		tx = S_lookup[num].x;
		ty = S_lookup[num].y;
		tmp[tx][ty] = ball_sz;
		num++;
		if (num == N * N) break;

		tx = S_lookup[num].x;
		ty = S_lookup[num].y;
		tmp[tx][ty] = ball_num;
		num++;
		if (num == N * N) break;
	}
	memcpy(board, tmp, sizeof(tmp));
}


void simul()
{
	for (int m = 0; m < M; m++) {
		throw_ice(m);
		re_arrange();
		while (1) {
			if (!blow_up()) break;
			re_arrange();
		}
		trans_ball();
	}
}

void output()
{
	int total = 0;
	for (int i = 1; i <= 3; i++) {
		total += i * ans[i];
	}
	printf("%d\n", total);
}

int main()
{
	input();
	make_snail();
	simul();
	output();
	return 0;
}

50 * 50 맵에 대한 룩업테이블을 만들려면 어디까지 인덱스를 설정해야 할까 ? 

100일까 ? 아니면 2500일까 ? 

이걸 왜 틀리고 앉아있어가지고 시험 5일 전에 장장 7시간을 한문제에 태웠을까 ? ㅎ... ? 나레기...

 

덕분에 달팽이 사각형 오지게 연습함 ... ㅎ 좋은건가..