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

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

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

 

문제에서 하라는 대로 하면 되지만, 구현이 빡센 문제였다.

 

"만약, 구슬이 칸의 수보다 많아 칸에 들어가지 못하는 경우 그러한 구슬은 사라진다." 이 조건을 간과해서 런타임 에러가 났는데 이 부분만 주의하면 될 듯.

 

#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int N, M;
int board[50][50];
vector<vector<int>> info; // d, s
vector<int> flat_board;
vector<int> answer(4);

int dr[5] = { 0,-1,1,0,0 };
int dc[5] = { 0,0,0,-1,1 };

void initialize() {
	while (!flat_board.empty()) {
		flat_board.pop_back();
	}

	for (int i = 0; i < 50; i++) {
		memset(board[i], 0, sizeof(int)*50);
	}
}

void input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> board[i][j];
		}
	}

	int d, s;
	for (int i = 0; i < M; i++) {
		cin >> d >> s;
		info.push_back({ d,s });
	}
}

void flat() {
	flat_board.push_back(0); //상어 넣기

	//초기위치 : 상어 위치
	int row = (N + 1) / 2;
	int col = (N + 1) / 2;

	int cnt = 1;
	int increase = 1;

	while (cnt < N * N) {
		if (increase % 2 == 1) { //홀수 -> 왼쪽, 아래
			for (int i = 1; i <= increase & cnt < N * N; i++) { //왼쪽
				if (board[row][col - i] > 0)
					flat_board.push_back(board[row][col - i]);
				cnt++;
			}

			for (int i = 1; i <= increase & cnt < N * N; i++) { //아래쪽
				if (board[row + i][col - increase])
					flat_board.push_back(board[row + i][col - increase]);
				cnt++;
			}

			row = row + increase;
			col = col - increase;
		}
		else { //오른쪽, 위
			for (int i = 1; i <= increase & cnt < N * N; i++) { //오른쪽
				if (board[row][col + i])
					flat_board.push_back(board[row][col + i]);
				cnt++;
			}

			for (int i = 1; i <= increase & cnt < N * N; i++) { //위
				if (board[row - i][col + increase])
					flat_board.push_back(board[row - i][col + increase]);
				cnt++;
			}
			row = row - increase;
			col = col + increase;
		}
		increase++;
	}
}

bool boom() {
	int idx = 1;
	int cnt = 1;
	bool flag = false;

	while (idx < flat_board.size()) {
		int start = idx;
		while (idx + 1 < flat_board.size() && flat_board[idx] == flat_board[idx + 1]) {
			idx++;
			cnt++;
		}

		if (cnt >= 4) {
			for (int i = start; i <= idx; i++) {
				answer[flat_board[i]]++;
				flat_board[i] = 0;
			}
			flag = true;
			idx--;
		}
		cnt = 1;
		idx++;
	}

	return flag;
}

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

	int cnt = 1;
	int i = 1;
	while (i < flat_board.size()) {
		int num = flat_board[i];
		while (i < flat_board.size() - 1 && flat_board[i] == flat_board[i + 1]) {
			cnt++;
			i++;
		}
		result.push_back(cnt);
		result.push_back(num);
		cnt = 1;
		i++;
	}

	return result;
}

void makeBoard(vector<int> v) {
	int row = (N + 1) / 2;
	int col = (N + 1) / 2;

	//board와 flat_board 초기화
	initialize();

	int increase = 1;
	int idx = 0;
	while (idx < v.size() && idx < N * N -1) {
		if (increase % 2 == 1) { //홀수 -> 왼쪽, 아래
			for (int i = 1; i <= increase && idx < v.size() && idx < N * N - 1; i++) { //왼쪽
				board[row][col - i] = v[idx];
				idx++;
			}

			for (int i = 1; i <= increase && idx < v.size() && idx < N * N - 1; i++) { //아래쪽
				board[row + i][col - increase] = v[idx];
				idx++;
			}

			row = row + increase;
			col = col - increase;
		}
		else { //오른쪽, 위
			for (int i = 1; i <= increase && idx < v.size() && idx < N * N - 1; i++) { //오른쪽
				board[row][col + i] = v[idx];
				idx++;
			}

			for (int i = 1; i <= increase && idx < v.size() && idx < N * N - 1; i++) { //위
				board[row - i][col + increase] = v[idx];
				idx++;
			}
			row = row - increase;
			col = col + increase;
		}
		increase++;
	}

}

void print() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cout << board[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

void solve(int d, int s) {
	//상어 위치
	int row = (N + 1) / 2;
	int col = (N + 1) / 2;

	//구슬 파괴
	for (int i = 1; i <= s; i++) {
		row += dr[d];
		col += dc[d];
		board[row][col] = 0;
	}

	// 빈칸 채우기
	flat();

	// 구슬 폭발
	while (boom()) {
		for (vector<int>::iterator iter = flat_board.begin() + 1; iter != flat_board.end();) {
			if (*iter == 0) {
				iter = flat_board.erase(iter);
			}
			else {
				iter++;
			}
		}
	}

	// 구슬 변화 (구슬 개수, 구슬 번호)
	vector<int> changedVec = change();

	//board로 만들기
	makeBoard(changedVec);
}

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

	//freopen("input.txt", "r", stdin);
	input();
	for (int j = 0; j < M; j++) {
		solve(info[j][0], info[j][1]);
	}
	cout << 1 * answer[1] + 2 * answer[2] + 3 * answer[3] << endl;
	return 0;
}