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

아놀드·2021년 11월 29일
1

백준

목록 보기
65/73
post-thumbnail

1. 문제 링크

문제 링크

2. 풀이

전형적인 삼성 기출 문제 유형의 빡센 구현 문제입니다.
하나씩 차근차근 해봅시다.

1. 블리자드 마법

int d, s;

cin >> d >> s;

d--;
for (int i = 1; i <= s; i++) {
	int y = n / 2 + my[d] * i;
	int x = n / 2 + mx[d] * i;

	board[y][x] = 0;
}

단순히 d방향으로 s만큼 0으로 만들어줍니다.

2. 구슬을 큐에 모으기


마법사 상어와 토네이도 포스팅에서 설명한 방식입니다.
위 규칙대로 맵을 순회하면서 구슬들을 queue에 모읍니다.

bool gatherBeadToQueue() {
	for (int i = 0; i < len; i++) {
		y += ry[d];
		x += rx[d];

		if (x < 0) return true; // 루프를 다 돌았을 때

		if (board[y][x] > 0) { // 구슬일 때
			q.push(board[y][x]);
		}
	}

	return false;
}

void gatherBead() {
	y = n / 2;
	x = n / 2;
	len = 1;
	d = 0;

	while (1) {
		if (gatherBeadToQueue()) break; // 루프 다 돌았으면 종료

		d = (d + 1) % 4; // 방향 꺾기

		gatherBeadToQueue();

		d = (d + 1) % 4; // 방향 꺾기
		len++; // 루프 길이 증가
	}
}

3. 모은 구슬을 안에서부터 배치하기

bool deployBead() {
	for (int i = 0; i < len; i++) {
		y += ry[d];
		x += rx[d];

		if (x < 0) return true; // 루프를 다 돌았을 때

		if (q.empty()) { // 큐가 비었다면 0으로 만들기
			board[y][x] = 0;
		}
		else { 
			board[y][x] = q.front(); 
			q.pop();
		}
	}

	return false;
}

void moveBead() {
	y = n / 2;
	x = n / 2;
	len = 1;
	d = 0;

	while (1) {
		if (deployBead()) break;

		d = (d + 1) % 4;

		deployBead();

		d = (d + 1) % 4;
		len++;
	}
}

2번과 똑같이 안쪽에서부터 달팽이 모양으로 순회하며
큐에서 pop하면서 구슬을 배치합니다.

4. 구슬 폭발

void accAnswer() {
	int isExplode = st.size() >= 4; // 스택의 사이즈가 4이상이면 폭발

	isContinue = isContinue || isExplode; // 폭발했다면 계속 진행
	ans += isExplode ? get<2>(st.top()) * st.size() : 0; // 정답 증가

	while (!st.empty()) {
		if (isExplode) board[get<0>(st.top())][get<1>(st.top())] = 0; // 폭발일 때 0으로 바꾸기
		st.pop();
	}
}

bool explodeBead() {
	for (int i = 0; i < len; i++) {
		y += ry[d];
		x += rx[d];

		if (x < 0 || board[y][x] == 0) { // 루프를 다 돌았거나 구슬이 더 이상 없을 때
			if (!st.empty()) accAnswer();

			return true;
		}

		if (!st.empty() && get<2>(st.top()) != board[y][x]) { 
			accAnswer(); // 스택이 비어있지 않고 현재 구슬과 스택의 top의 구슬이 다를 때
		}

		st.push({ y, x, board[y][x] });
	}

	return false;
}

void explodeBeadUntillEnable() {
	while (1) {
		y = n / 2;
		x = n / 2;
		len = 1;
		d = 0;
		isContinue = 0;

		while (1) {
			if (explodeBead()) break;

			d = (d + 1) % 4;

			if (explodeBead()) break;

			d = (d + 1) % 4;
			len++;
		}

		if (!isContinue) break; // 구슬이 안 터졌다면 break

		gatherBead(); // 구슬 큐에 모으기
		moveBead(); // 안에서부터 배치하기
	}
}

이 부분이 살짝 어렵습니다.
달팽이 모양으로 순회하는 건 똑같습니다.
근데 이번엔 queue가 아니라 stack에 담습니다.
stacktop과 현재 구슬이 일치할 때까지 stackpush하다가
달라진 순간에 stack의 사이즈가 4이상이라면 폭발시키면 됩니다.

5. 새구슬 넣기

bool pushNewBeadToQueue() {
	int size = st2.size();
	int bead = st2.top();

	q.push(size);
	q.push(bead);

	while (!st2.empty()) st2.pop();

	return q.size() >= n * n - 1; // 큐 사이즈가 맵 사이즈보다 크다면 종료
}

bool gatherNewBead() {
	for (int i = 0; i < len; i++) {
		y += ry[d];
		x += rx[d];

		if (x < 0 || board[y][x] == 0) { // 루프 아웃이거나 구슬이 없을 때
			if (!st2.empty()) pushNewBeadToQueue();

			return true;
		}

		if (!st2.empty() && st2.top() != board[y][x] && pushNewBeadToQueue()) return true;

		st2.push(board[y][x]);
	}

	return false;
}

void pushNewBead() {
	y = n / 2;
	x = n / 2;
	len = 1;
	d = 0;

	while (1) {
		if (gatherNewBead()) break;

		d = (d + 1) % 4;

		if (gatherNewBead()) break;

		d = (d + 1) % 4;
		len++;
	}

	moveBead(); // 안에서부터 새구슬 넣기
}

이번에도 stack을 사용합니다.
stacktop과 현재 구슬이 일치할 때까지 stackpush하다가
달라진 순간에 queuestack의 사이즈와 top을 넣습니다.
순회 완료하면 안에서부터 새구슬을 넣으면 됩니다.

3. 전체 코드

#include <bits/stdc++.h>

using namespace std;

int n, m, ans;
int y, x, len, d, isContinue;
int my[4] = { -1, 1, 0, 0 };
int mx[4] = { 0, 0, -1, 1 };
int ry[4] = { 0, 1, 0, -1 };
int rx[4] = { -1, 0, 1, 0 };
int board[49][49];
queue<int> q;
stack<tuple<int, int, int>> st;
stack<int> st2;

bool gatherBeadToQueue() {
	for (int i = 0; i < len; i++) {
		y += ry[d];
		x += rx[d];

		if (x < 0) return true;

		if (board[y][x] > 0) {
			q.push(board[y][x]);
		}
	}

	return false;
}

bool deployBead() {
	for (int i = 0; i < len; i++) {
		y += ry[d];
		x += rx[d];

		if (x < 0) return true;

		if (q.empty()) {
			board[y][x] = 0;
		}
		else {
			board[y][x] = q.front();
			q.pop();
		}
	}

	return false;
}

void gatherBead() {
	y = n / 2;
	x = n / 2;
	len = 1;
	d = 0;

	while (1) {
		if (gatherBeadToQueue()) break;

		d = (d + 1) % 4;

		gatherBeadToQueue();

		d = (d + 1) % 4;
		len++;
	}
}

void moveBead() {
	y = n / 2;
	x = n / 2;
	len = 1;
	d = 0;

	while (1) {
		if (deployBead()) break;

		d = (d + 1) % 4;

		deployBead();

		d = (d + 1) % 4;
		len++;
	}
}

void accAnswer() {
	int isExplode = st.size() >= 4;

	isContinue = isContinue || isExplode;
	ans += isExplode ? get<2>(st.top()) * st.size() : 0;

	while (!st.empty()) {
		if (isExplode) board[get<0>(st.top())][get<1>(st.top())] = 0;
		st.pop();
	}
}

bool explodeBead() {
	for (int i = 0; i < len; i++) {
		y += ry[d];
		x += rx[d];

		if (x < 0 || board[y][x] == 0) {
			if (!st.empty()) accAnswer();

			return true;
		}

		if (!st.empty() && get<2>(st.top()) != board[y][x]) {
			accAnswer();
		}

		st.push({ y, x, board[y][x] });
	}

	return false;
}

void explodeBeadUntillEnable() {
	while (1) {
		y = n / 2;
		x = n / 2;
		len = 1;
		d = 0;
		isContinue = 0;

		while (1) {
			if (explodeBead()) break;

			d = (d + 1) % 4;

			if (explodeBead()) break;

			d = (d + 1) % 4;
			len++;
		}

		if (!isContinue) break;

		gatherBead();
		moveBead();
	}
}

bool pushNewBeadToQueue() {
	int size = st2.size();
	int bead = st2.top();

	q.push(size);
	q.push(bead);

	while (!st2.empty()) st2.pop();

	return q.size() >= n * n - 1;
}

bool gatherNewBead() {
	for (int i = 0; i < len; i++) {
		y += ry[d];
		x += rx[d];

		if (x < 0 || board[y][x] == 0) {
			if (!st2.empty()) pushNewBeadToQueue();

			return true;
		}

		if (!st2.empty() && st2.top() != board[y][x] && pushNewBeadToQueue()) return true;

		st2.push(board[y][x]);
	}

	return false;
}

void pushNewBead() {
	y = n / 2;
	x = n / 2;
	len = 1;
	d = 0;

	while (1) {
		if (gatherNewBead()) break;

		d = (d + 1) % 4;

		if (gatherNewBead()) break;

		d = (d + 1) % 4;
		len++;
	}

	moveBead();
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> board[i][j];

	while (m--) {
		int d, s;

		cin >> d >> s;

		d--;
		for (int i = 1; i <= s; i++) {
			int y = n / 2 + my[d] * i;
			int x = n / 2 + mx[d] * i;

			board[y][x] = 0;
		}

		gatherBead();
		moveBead();
		explodeBeadUntillEnable();
		pushNewBead();
	}

	cout << ans;

	return 0;
}

계속 빙글빙글 돌려대서 제 머리도 빙글빙글 돌 뻔한 문제였습니다.

profile
함수형 프로그래밍, 자바스크립트에 관심이 많습니다.

0개의 댓글