[삼성 코테 기출] 21611 - 마법사 상어와 블리자드

 

구현 문제에서 행, 열을 다루는 방법이 일반적이지 않은 문제이다.

구슬이 사라진 후에 순서에 맞는 동작을 시키는 것이 중요하고 연쇄되는 동작에 대해

잘 구현하여야 디버깅의 늪에 빠지지 않을 수 있다.

 

메모리 : 2036 KB

시간 : 12ms

언어 : C++17

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int map[50][50];
int N, M;
int sr, sc;
int answer[3] = { 0,0,0 };

deque<int> balls;
vector<int> tmp;


void set_balls() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			map[i][j] = 0;
		}
	}

	if (balls.size() == 0) return;

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

	int r = sr;
	int c = sc;
	int d = 0;
	int s = 0;
	while (!(r == 0 && c == 0)) {
		if (d % 2 == 0) s++;
		for (int t = 0; t < s; t++) {
			r += dr[d];
			c += dc[d];
			map[r][c] = balls[0]; 
			balls.pop_front();
			if (balls.empty()) return;
			if (r == 0 && c == 0) return;
		}
		d = (d + 1) % 4;
	}
}

bool explosion() {
	int size = balls.size();
	int cnt = 1;
	bool flag = false;

	if (size == 0) return false;

	tmp.clear();
	while (!balls.empty()) {
		tmp.push_back(balls[0]);
		balls.pop_front();
	}
	int n = tmp[0];
	tmp.push_back(0);
	for (int i = 1; i < size + 1; i++) {
		if (n == tmp[i]) cnt++;
		else {
			if (cnt < 4) {
				for(int t = cnt; t > 0; t--) balls.push_back(tmp[i - t]);
			}
			else {
				flag = true;
				answer[n - 1] += cnt;
			}
			n = tmp[i];
			cnt = 1;
		}
	}

	return flag;
}

void get_balls() {

	int dr[4] = { 0, 1, 0, -1 };
	int dc[4] = { -1, 0, 1, 0 };
	balls.clear();
	int r = sr;
	int c = sc;
	int d = 0;
	int s = 0;
	while (!(r == 0 && c == 0)) {
		if (d % 2 == 0) s++;
		for(int t = 0; t < s; t++){
			r += dr[d];
			c += dc[d];
			if(map[r][c] != 0) balls.push_back(map[r][c]);
			if (r == 0 && c == 0) break;
		}
		d = (d + 1) % 4;
	}
}

void destroy(int d, int s) {

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

	int r = sr;
	int c = sc;

	for (int i = 1; i <= s; i++) {
		r += dr[d];
		c += dc[d];

		map[r][c] = 0;
	}

}


void set_group_balls() {
	get_balls();

	int size = balls.size();
	int cnt = 1;

	if (size == 0) return;

	tmp.clear();
	while (!balls.empty()) {
		tmp.push_back(balls[0]);
		balls.pop_front();
	}
	int n = tmp[0];
	tmp.push_back(0);

	for (int i = 1; i < size + 1; i++) {
		if (n == tmp[i]) cnt++;
		else {
			balls.push_back(cnt);
			balls.push_back(n);

			n = tmp[i];
			cnt = 1;
		}
	}

	set_balls();
}

int main(void) {
	
	cin >> N >> M;
	
	sr = sc = (N - 1) / 2;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	
	int d, s;
	for (int i = 0; i < M; i++) {
		cin >> d >> s;
		destroy(d - 1, s);
		get_balls();
		while(explosion());
		set_balls();
		set_group_balls();
	}

	int ans = 0;
	for (int i = 0; i < 3; i++) ans += answer[i] * (i + 1);
	cout << ans << "\n";

	return 0;
}