전형적인 삼성 기출 문제 유형의 빡센 구현 문제입니다.
하나씩 차근차근 해봅시다.
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
으로 만들어줍니다.
마법사 상어와 토네이도 포스팅에서 설명한 방식입니다.
위 규칙대로 맵을 순회하면서 구슬들을 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++; // 루프 길이 증가
}
}
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
하면서 구슬을 배치합니다.
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
에 담습니다.
stack
의 top
과 현재 구슬이 일치할 때까지 stack
에 push
하다가
달라진 순간에 stack
의 사이즈가 4
이상이라면 폭발시키면 됩니다.
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
을 사용합니다.
stack
의 top
과 현재 구슬이 일치할 때까지 stack
에 push
하다가
달라진 순간에 queue
에 stack
의 사이즈와 top
을 넣습니다.
순회 완료하면 안에서부터 새구슬을 넣으면 됩니다.
#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;
}
계속 빙글빙글 돌려대서 제 머리도 빙글빙글 돌 뻔한 문제였습니다.