백준 - 마법사 상어와 블리자드 (21611) [C++]

 이 문제는 구현, 시뮬레이션 문제이다. 요구사항이 굉장히 까다로운데, 핵심적인 부분은 2차원 배열의 중앙부터 반시계 방향으로 배열을 읽는 방법을 구현하는 것과 구슬 폭발을 구현하는 것이다. 

 

 첫 번째는 나의 경우 nextPos 함수와 make 함수를 통해 구현하였다. nextPos는 현재 위치 기준으로 direction에 따라 다음 위치를 리턴하는 함수이고, make는 nextPos를 이용하여 전체 2차원 배열을 반시계 방향으로 순회하는 함수이다. 반시계 순회의 규칙성을 보면 중간에서 시작하여 1, 1, 2, 2, 3, 3, 4, 4, .... 의 양만큼 앞으로 가고, 방향은 왼, 아, 오, 위 순으로 동작한다. 이를 그대로 구현하면 쉽게 반시계 방향으로 읽을 수 있다.

 

 두 번째는 구슬 폭발 구현인데, 이 부분이 가장 중요하고 내가 약간의 검색을 통해 힌트를 얻은 부분이다. 처음에는 stack을 이용해서 구현하였으나 오답이 나왔다. 이는 구슬이 4개 이상인 모든 그룹에서 동시에 폭발해야 하는데, stack을 사용하면 순차적으로 폭발하여 나머지가 남을 수 있기 때문이었다. 그래서 이 문제의 경우 배열을 이용하여 폭파할 부분을 체크한 뒤 한번에 처리해야한다. 

 여기서 erase를 사용하여 94퍼에서 오답이 나왔는데, erase 메소드에 대한 정확한 지식이 없어 틀린 답이라고 생각했고, deleted 배열을 통해 체크 후 한번에 처리하는 방식으로 풀어 정답이 나왔다.

 

 이 문제를 풀면서 아쉬웠던 점은 2차원 배열을 make 함수로 읽은 1차원 배열을 통해 문제를 풀었다면 코드 길이가 상당히 줄었을 것이라는 것이었다. 또한 erase 사용법을 정확히 모른 상태로 구현하여 로직이 맞았음에도 틀린 답을 도출했다는 점이었다. 

 

 앞으로 문제를 풀 때 STL 함수에 의존하지 않고 직접 구현해보는 연습을 해야 할 것 같다.

 

 

 

 

#include <iostream>
#include <vector>
#include <utility>
#include <stack>
#include <algorithm>

using namespace std;

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

int N, M;
int answer[4];
vector<vector<int>> matrix;

pair<int, int> nextPos(int y, int x, int direction) {
	switch (direction) {
	case UP:
		y--;
		break;
	case DOWN:
		y++;
		break;
	case LEFT:
		x--;
		break;
	case RIGHT:
		x++;
	}

	return { y, x };
}

bool inRange(int y, int x) {
	if (0 <= y && y < N && 0 <= x && x < N) {
		return true;
	}
	return false;
}

vector<int> make() {
	vector<int> result;

	int startY = N / 2;
	int startX = N / 2;

	int di[] = { LEFT, DOWN, RIGHT, UP };
	int index = 0;

	int num = 1;

	for (int cnt = 1; cnt <= N; cnt++) {
		int nextDirect1 = di[index];
		index++;
		index %= 4;
		int nextDirect2 = di[index];
		index++;
		index %= 4;

		// 1
		for (int i = 0; i < cnt; i++) {
			pair<int, int> next = nextPos(startY, startX, nextDirect1);
			
			if (!inRange(next.first, next.second)) {
				return result;
			}

			result.push_back(matrix[next.first][next.second]);

			startY = next.first;
			startX = next.second;
		}


		// 2
		for (int i = 0; i < cnt; i++) {
			pair<int, int> next = nextPos(startY, startX, nextDirect2);

			if (!inRange(next.first, next.second)) {
				return result;
			}

			result.push_back(matrix[next.first][next.second]);

			startY = next.first;
			startX = next.second;
		}
	}
}

vector<int> traversal() {
	vector<int> result;
	int startY = N / 2;
	int startX = N / 2;

	int di[] = { LEFT, DOWN, RIGHT, UP };
	int index = 0;

	int num = 1;

	for (int cnt = 1; cnt <= N; cnt++) {
		int nextDirect1 = di[index];
		index++;
		index %= 4;
		int nextDirect2 = di[index];
		index++;
		index %= 4;

		// 1
		for (int i = 0; i < cnt; i++) {
			pair<int, int> next = nextPos(startY, startX, nextDirect1);

			if (!inRange(next.first, next.second)) {
				return result;
			}

			if (matrix[next.first][next.second] != 0) {
				result.push_back(matrix[next.first][next.second]);
			}

			startY = next.first;
			startX = next.second;
		}


		// 2
		for (int i = 0; i < cnt; i++) {
			pair<int, int> next = nextPos(startY, startX, nextDirect2);

			if (!inRange(next.first, next.second)) {
				return result;
			}

			if (matrix[next.first][next.second] != 0) {
				result.push_back(matrix[next.first][next.second]);
			}

			startY = next.first;
			startX = next.second;
		}
	}
}

vector<vector<int>> fill(vector<int> temp) {
	vector<vector<int>> result(N, vector<int>(N));

	int tempIndex = 0;
	int startY = N / 2;
	int startX = N / 2;

	int di[] = { LEFT, DOWN, RIGHT, UP };
	int index = 0;

	int num = 1;

	for (int cnt = 1; cnt <= N; cnt++) {
		int nextDirect1 = di[index];
		index++;
		index %= 4;
		int nextDirect2 = di[index];
		index++;
		index %= 4;

		// 1
		for (int i = 0; i < cnt; i++) {
			pair<int, int> next = nextPos(startY, startX, nextDirect1);

			if (!inRange(next.first, next.second)) {
				return result;
			}

			if (tempIndex < temp.size()) {
				result[next.first][next.second] = temp[tempIndex];
				tempIndex++;
			}
			else {
				result[next.first][next.second] = 0;
			}

			startY = next.first;
			startX = next.second;
		}


		// 2
		for (int i = 0; i < cnt; i++) {
			pair<int, int> next = nextPos(startY, startX, nextDirect2);

			if (!inRange(next.first, next.second)) {
				return result;
			}

			if (tempIndex < temp.size()) {
				result[next.first][next.second] = temp[tempIndex];
				tempIndex++;
			}
			else {


				result[next.first][next.second] = 0;
			}

			startY = next.first;
			startX = next.second;
		}
	}
}

void print() {
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cout << matrix[y][x] << " ";
		}
		cout << '\n';
	}
	cout << '\n';
}

void magic(int d, int s) {
	int startY = N / 2;
	int startX = N / 2;

	for (int i = 0; i < s; i++) {
		pair<int, int> next = nextPos(startY, startX, d);

		matrix[next.first][next.second] = 0;
		startY = next.first;
		startX = next.second;
	}
}

void rebuild() {
	vector<int> result = traversal();

	vector<vector<int>> tempMatrix = fill(result);

	matrix = tempMatrix;
}

struct node {
	int startIndex;
	int endIndex;
	int num;
	int cnt;
};

vector<int> explodeProcess(vector<int> input) {
	vector<int> deleted(input.size(), false);
	vector<int> result;
	int endSize;

	bool flag = true;

	while (flag) {
		flag = false;
		vector<node> exp;
		node temp = { -1, -1, -1, -1 };

		for (int i = 0; i < input.size(); i++) {
			if (input[i] == 0) {
				endSize = i;
				break;
			}

			if (deleted[i]) {
				continue;
			}

			if (temp.startIndex == -1) {
				temp = { i, -1, input[i], 1 };
			}
			else {
				if (temp.num == input[i]) {
					temp.cnt++;
				}
				else {
					if (temp.cnt >= 4) {
						flag = true;
						temp.endIndex = i - 1;
						exp.push_back(temp);
					}
					temp = { i, -1, input[i], 1 };
				}
			}
		}

		if (temp.cnt >= 4) {
			flag = true;
			temp.endIndex = endSize;
			exp.push_back(temp);
		}

		for (node &ex : exp) {
			answer[ex.num] += ex.cnt;

			for (int i = ex.startIndex; i <= ex.endIndex; i++) {
				deleted[i] = true;
			}
		}
	}

	for (int i = 0; i < deleted.size(); i++) {
		if (!deleted[i]) {
			result.push_back(input[i]);
		}
	}

	return result;
}

vector<pair<int, int>> changeProcess() {
	
	vector<pair<int, int>> result;
	pair<int, int> temp = { 0, 0 };
	int startY = N / 2;
	int startX = N / 2;

	int di[] = { LEFT, DOWN, RIGHT, UP };
	int index = 0;

	for (int cnt = 1; cnt <= N; cnt++) {
		int nextDirect1 = di[index];
		index++;
		index %= 4;
		int nextDirect2 = di[index];
		index++;
		index %= 4;

		// 1
		for (int i = 0; i < cnt; i++) {
			pair<int, int> next = nextPos(startY, startX, nextDirect1);

			if (!inRange(next.first, next.second)) {
				if (temp.second != 0)
					result.push_back(temp);
				return result;
			}

			int tempNum = matrix[next.first][next.second];

			if (tempNum != 0) {
				if (temp.second == 0) {
					temp.first = 1;
					temp.second = tempNum;
				}
				else {
					if (temp.second == tempNum) {
						temp.first++;
					}
					else {
						result.push_back(temp);
						temp.first = 1;
						temp.second = tempNum;
					}
				}
			}

			startY = next.first;
			startX = next.second;
		}


		// 2
		for (int i = 0; i < cnt; i++) {
			pair<int, int> next = nextPos(startY, startX, nextDirect2);

			if (!inRange(next.first, next.second)) {
				if (temp.second != 0)
					result.push_back(temp);
				return result;
			}

			int tempNum = matrix[next.first][next.second];

			if (tempNum != 0) {
				if (tempNum != 0) {
					if (temp.second == 0) {
						temp.first = 1;
						temp.second = tempNum;
					}
					else {
						if (temp.second == tempNum) {
							temp.first++;
						}
						else {
							result.push_back(temp);
							temp.first = 1;
							temp.second = tempNum;
						}
					}
				}
			}

			startY = next.first;
			startX = next.second;
		}
	}
}

void explode() {
	vector<int> temp = make();

	vector<int> processed = explodeProcess(temp);

	vector<vector<int>> tempMatrix = fill(processed);

	matrix = tempMatrix;
}

void change() {
	vector<pair<int, int>> temp = changeProcess();

	vector<int> input;

	for (pair<int, int> &t : temp) {
		input.push_back(t.first);
		input.push_back(t.second);
	}

	vector<vector<int>> tempMatrix = fill(input);

	matrix = tempMatrix;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;

	matrix = vector<vector<int>>(N, vector<int>(N));

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> matrix[y][x];
		}
	}

	for (int i = 0; i < M; i++) {
		int d, s;

		cin >> d >> s;
		d--;

		// 1. magic
		magic(d, s);

		// 2. rebuild
		rebuild();

		// 3. explode(inner rebuild) - 동시에 터져야 한다.
		explode();

		// 4. change(inner)
		change();
	}

	int result = answer[1] + answer[2] * 2 + answer[3] * 3;

	cout << result << '\n';

	return 0;
}