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

sol : 159' 59''

• 수행 시간 : 8ms
• 메모리 : 2036KB

Learnings

• 모두 같은 구슬일 경우 점수 합산 로직을 빼먹어서 1시간 넘게 디버깅했다.

#include <iostream>
#include <vector>

using namespace std;

#define MAX_N 50
#define MAX_M 101

#define SHARK -1
#define EMPTY 0
#define RED 1
#define BLUE 2
#define PURPLE 3

#define UP 1
#define DOWN 2
#define LEFT 3
#define RIGHT 4

// 상, 하, 좌, 우
const int ds[5][2] = { {0, 0}, { -1, 0 }, {1, 0}, {0, -1}, {0, 1} };
int grid[MAX_N][MAX_N];
int spell[MAX_M][2];
int exBeeds[4];
int shark_i, shark_j;
vector<int> flatArr;

int n, m;
bool boom;

void Debug() {
	cout << endl << "DEBUG" << endl;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == (n + 1) / 2 && j == (n + 1) / 2) cout << "S ";
			else cout << grid[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl;
}

void DebugFlatArr() {
	cout << endl << "DEBUG FA" << endl;
	for (int i = 0; i < flatArr.size(); i++) {
		cout << flatArr[i] << ' ';
	}
	cout << endl << "DEBUG FA FIN" << endl;
}

void Init() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> grid[i][j];
		}
	}
	shark_i = (n + 1) / 2, shark_j = (n + 1) / 2;
	grid[shark_i][shark_j] = SHARK;

	for (int i = 1; i <= m; i++) {
		cin >> spell[i][0] >> spell[i][1];
	}
}

void Destroy(int turn) {
	int c_dir = spell[turn][0], c_dist = spell[turn][1];
	int ci = shark_i, cj = shark_j;

	for (int dist = 1; dist <= c_dist; dist++) {
		int ni = ci + ds[c_dir][0], nj = cj + ds[c_dir][1];
		grid[ni][nj] = EMPTY;
		ci = ni, cj = nj;
	}
}

void PrintResult() {
	int result = 0;
	for (int i = 1; i <= 3; i++) {
		result += exBeeds[i] * i;
	}
	cout << result;
}

void Move() {
	bool leftDown = false;
	int ci = shark_i, cj = shark_j;
	flatArr.clear();

	// Flatten
	for (int d = 1; d < n; d++) {
		leftDown ^= 1;
		if (leftDown) {
			// LEFT
			for (int sd = 0; sd < d; sd++) {
				ci += ds[LEFT][0], cj += ds[LEFT][1];

				if (grid[ci][cj] == EMPTY) continue;
				flatArr.push_back(grid[ci][cj]);
			}

			// DOWN
			for (int sd = 0; sd < d; sd++) {
				ci += ds[DOWN][0], cj += ds[DOWN][1];
				
				if (grid[ci][cj] == EMPTY) continue;
				flatArr.push_back(grid[ci][cj]);
			}
		}
		else {
			// RIGHT
			for (int sd = 0; sd < d; sd++) {
				ci += ds[RIGHT][0], cj += ds[RIGHT][1];
				
				if (grid[ci][cj] == EMPTY) continue;
				flatArr.push_back(grid[ci][cj]);
			}

			// UP
			for (int sd = 0; sd < d; sd++) {
				ci += ds[UP][0], cj += ds[UP][1];

				if (grid[ci][cj] == EMPTY) continue;
				flatArr.push_back(grid[ci][cj]);
			}
		}
	}
	for (int j = n - 1; j > 0; j--) {
		if (grid[1][j] == EMPTY) continue;

		flatArr.push_back(grid[1][j]);
	}
}

void Explode() {
	boom = false;

	if (flatArr.empty()) return;

	vector<int> tempArr;
	int curBeed = flatArr[0];
	int curCnt = 1, start_idx = 0;
	for (int i = 1; i < flatArr.size(); i++) {
		if (flatArr[i] == curBeed) {
			curCnt++;
		}
		else {
			if (curCnt < 4) {
				for (int di = 0; di < curCnt; di++) {
					tempArr.push_back(flatArr[start_idx + di]);
				}
				curBeed = flatArr[i];
				curCnt = 1, start_idx = i;
			}
			else {
				exBeeds[curBeed] += curCnt;
				boom = true;
				curBeed = flatArr[i];
				curCnt = 1, start_idx = i;
			}
		}
	}
	// 마지막 연속 집단 처리
	if (curCnt < 4) {
		for (int di = 0; di < curCnt; di++) {
			tempArr.push_back(flatArr[start_idx + di]);
		}
	}
	else {
		exBeeds[curBeed] += curCnt;
		boom = true;
	}


	flatArr.clear();
	for (int i = 0; i < tempArr.size(); i++) {
		flatArr.push_back(tempArr[i]);
	}
}

void Change() {
	if (flatArr.empty()) return;

	vector<int> tempArr;
	int curBeed = flatArr[0], curCnt = 1;
	for (int i = 1; i < flatArr.size(); i++) {
		if (flatArr[i] == curBeed) {
			curCnt++;
		}
		else {
			tempArr.push_back(curCnt);
			if (tempArr.size() == n * n - 1) break;
			tempArr.push_back(curBeed);
			if (tempArr.size() == n * n - 1) break;

			curBeed = flatArr[i], curCnt = 1;
		}
	}
	// 마지막 연속 집단 처리
	if (tempArr.size() < n * n - 1) {
		tempArr.push_back(curCnt);
		if (tempArr.size() < n * n - 1) {
			tempArr.push_back(curBeed);
		}
	}

	flatArr.clear();
	for (int i = 0; i < tempArr.size(); i++) {
		flatArr.push_back(tempArr[i]);
	}
}

void Draw() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			grid[i][j] = EMPTY;
		}
	}
	grid[shark_i][shark_j] = SHARK;
	
	if (flatArr.empty()) return;
	
	bool leftDown = false;
	int ci = shark_i, cj = shark_j;
	int flatArrIdx = 0;

	for (int d = 1; d < n; d++) {
		leftDown ^= 1;
		if (leftDown) {
			// LEFT
			for (int sd = 0; sd < d; sd++) {
				ci += ds[LEFT][0], cj += ds[LEFT][1];
				grid[ci][cj] = flatArr[flatArrIdx++];
				if (flatArrIdx >= flatArr.size()) return;
			}

			// DOWN
			for (int sd = 0; sd < d; sd++) {
				ci += ds[DOWN][0], cj += ds[DOWN][1];
				grid[ci][cj] = flatArr[flatArrIdx++];
				if (flatArrIdx >= flatArr.size()) return;
			}
		}
		else {
			// RIGHT
			for (int sd = 0; sd < d; sd++) {
				ci += ds[RIGHT][0], cj += ds[RIGHT][1];
				grid[ci][cj] = flatArr[flatArrIdx++];
				if (flatArrIdx >= flatArr.size()) return;
			}

			// UP
			for (int sd = 0; sd < d; sd++) {
				ci += ds[UP][0], cj += ds[UP][1];
				grid[ci][cj] = flatArr[flatArrIdx++];
				if (flatArrIdx >= flatArr.size()) return;
			}
		}
	}

	for (int j = n - 1; j > 0; j--) {
		grid[1][j] = flatArr[flatArrIdx++];
		if (flatArrIdx >= flatArr.size()) return;
	}
}

int main() {
	Init();

	for (int turn = 1; turn <= m; turn++) {
		Destroy(turn);

		Move();

		boom = true;
		while (boom) Explode();

		Change();

		Draw();
	}
	
	PrintResult();

	return 0;
}