백준 21611 - 마법사 상어와 블리자드 (풀이 과정에서 놓친 부분 확인하기)
문제링크
문제설명
- 빡구현 문제.. 자세한 문제 설명은 링크 참고
- 구슬은 1번, 2번, 3번 존재
- 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)를 출력
문제접근
블리자드 마법 순서
- 상어가 입력 받은 방향, 거리만큼 구슬을 모두 파괴한다.
AttackIce()함수
- 파괴된 구슬이 있던 칸은 빈칸이 되고, 상어의 위치를 중심으로 반시계 나선 방향으로 칸의 번호가 존재한다. 비어 있는 칸은 인접한 높은 번호의 칸에서 채워진다.
MoveMarble()함수
- 칸의 번호를 따라 같은 번호의 구슬이 4개 이상 존재하는 경우 폭발한다. 폭발하는 구슬의 번호와 개수를 기록해야 한다. 폭발 조건을 만족하는 연속 구슬이 없을 때까지 반복한다.
ExploreMarble()함수
- 구슬 변화 단계로 같은 번호의 연속 구슬(최대 1~3개 존재)끼리 하나의 그룹을 만든다. 만들어진 그룹은 A와 B로 변화한다. A는 그룹에 들어있는 구슬의 개수, B는 그룹을 이루고 있는 구슬이 번호이다. 이렇게 만들어진 새로운 구슬 정보를 업데이트 한다. 만약 칸의 개수를 초과하는 경우 나머지 구슬은 생략한다.
UpdateMarbleGroup()함수
놓쳤던 부분
- 63% 실패
- 구슬이 없는 경우를 고려하지 않았다.
- 94% 실패
- 모두 같은 구슬인 경우를 고려하지 않았다.
- 위 두가지 모두 업데이트 과정에서 구슬이 하나도 안남는 경우에 발생하는 문제였다. 각각의 함수에서 처음 상어가 위치하는 칸의 값(0) 을 스택에 담아두고 시작하는데 구슬이 하나도 존재하지 않게 되면 스택이 pop 작업을 거치지 않게 되어 스택에 0이 그대로 남아있게 된다. while 문 이후에 마지막 탐색을 한번 더 실행할 때 0에 대한 예외처리릃 해주지 않아서 발생한 문제였다.
구현
#include <iostream>
#include <vector>
#include <memory.h>
#include <queue>
#include <stack>
#include <algorithm>
#define MAX_N 51
#define DOWN 2
#define UP 1
#define LEFT 3
#define RIGHT 4
using namespace std;
// 상(1), 하(2), 좌(3), 우(4)
int dx[5] = { 0, -1, 1, 0, 0 };
int dy[5] = { 0, 0, 0, -1, 1 };
int N, M;
int numMarble = 0;
int board[MAX_N][MAX_N];
int nboard[MAX_N][MAX_N];
int brokenMarble[4];
int sharkXpos, sharkYpos;
vector<pair<int, int>> spellList;
void AttackIce(int dir, int s)
{
for (int i = 1; i <= s; i++)
{
int nxpos = sharkXpos + dx[dir] * i;
int nypos = sharkYpos + dy[dir] * i;
board[nxpos][nypos] = 0; // 빈칸으로 만들기
}
}
int ChangeDirection(int cdir)
{
if (cdir == LEFT) return DOWN;
else if (cdir == DOWN) return RIGHT;
else if (cdir == RIGHT) return UP;
else if (cdir == UP) return LEFT;
}
void UpdateNewBoard(vector<int>& eleList)
{
memset(nboard, 0, sizeof(nboard));
// update new board
int cxpos = sharkXpos;
int cypos = sharkYpos;
int cdir = LEFT;
int cnum = 0;
int count = 1;
while (cnum < numMarble)
{
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < count; j++)
{
int nxpos = cxpos + dx[cdir];
int nypos = cypos + dy[cdir];
nboard[nxpos][nypos] = eleList[cnum++];
cxpos = nxpos;
cypos = nypos;
if (cnum == numMarble) break;
}
cdir = ChangeDirection(cdir);
if (cnum == numMarble) break;
}
count++;
}
memcpy(board, nboard, sizeof(nboard));
}
void MoveMarble()
{
int nboard[MAX_N][MAX_N];
memset(nboard, 0, sizeof(nboard));
vector<int> eleList;
int cxpos = sharkXpos;
int cypos = sharkYpos;
int cdir = LEFT; // 상어 위치에서 탐색 시작 방향
int cnum = 0;
int count = 1;
while (cnum < numMarble)
{
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < count; j++)
{
int nxpos = cxpos + dx[cdir];
int nypos = cypos + dy[cdir];
if (board[nxpos][nypos] != 0) eleList.push_back(board[nxpos][nypos]);
cxpos = nxpos;
cypos = nypos;
cnum++;
if (cnum == numMarble) break;
}
cdir = ChangeDirection(cdir);
if (cnum == numMarble) break;
}
count++;
}
numMarble = eleList.size();
UpdateNewBoard(eleList);
}
bool ExploreMarble()
{
int nboard[MAX_N][MAX_N];
memset(nboard, 0, sizeof(nboard));
// 연속해서 나타나는 구슬 번호를 담는다.
stack<int> s;
vector<int> eleList;
int cxpos = sharkXpos;
int cypos = sharkYpos;
int cdir = LEFT; // 상어 위치에서 탐색 시작 방향
int cnum = 0;
int count = 1;
s.push(board[cxpos][cypos]);
while (cnum < numMarble)
{
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < count; j++)
{
int nxpos = cxpos + dx[cdir];
int nypos = cypos + dy[cdir];
if (s.top() == board[nxpos][nypos])
{
s.push(board[nxpos][nypos]);
}
else if (s.top() != board[nxpos][nypos])
{
if (s.size() < 4) // 폭발하지 않는 경우
{
while (!s.empty())
{
if(s.top() != 0) eleList.push_back(s.top());
s.pop();
}
}
else
{
while (!s.empty())
{
brokenMarble[s.top()]++;
s.pop();
}
}
s.push(board[nxpos][nypos]);
}
cxpos = nxpos;
cypos = nypos;
cnum++;
if (cnum == numMarble) break;
}
cdir = ChangeDirection(cdir);
if (cnum == numMarble) break;
}
count++;
}
if (s.size() < 4) // 폭발하지 않는 경우
{
while (!s.empty())
{
eleList.push_back(s.top());
s.pop();
}
}
else
{
while (!s.empty())
{
brokenMarble[s.top()]++;
s.pop();
}
}
if (numMarble > eleList.size())
{
numMarble = eleList.size();
UpdateNewBoard(eleList);
return true;
}
// 연속하는 구슬이 없는 경우, 구슬이 하나도 없는 경우
else if (numMarble == eleList.size() || numMarble==0)
{
return false;
}
}
void UpdateMarbleGroup()
{
// 연속해서 나타나는 구슬 번호를 담는다.
stack<int> s;
vector<pair<int, int>> groupList; // first: 그룹에 들어있는 구슬의 개수, second: 그룹을 이루고 있는 구슬의 번호
int cxpos = sharkXpos;
int cypos = sharkYpos;
int cdir = LEFT; // 상어 위치에서 탐색 시작 방향
int cnum = 0;
int count = 1;
s.push(board[cxpos][cypos]);
while (cnum < numMarble)
{
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < count; j++)
{
int nxpos = cxpos + dx[cdir];
int nypos = cypos + dy[cdir];
if (s.top() == board[nxpos][nypos])
{
s.push(board[nxpos][nypos]);
}
else if (s.top() != board[nxpos][nypos])
{
if(s.top() != 0) groupList.push_back(make_pair(s.size(), s.top()));
while (!s.empty())
{
s.pop();
}
s.push(board[nxpos][nypos]);
}
cxpos = nxpos;
cypos = nypos;
cnum++;
if (cnum == numMarble) break;
}
cdir = ChangeDirection(cdir);
if (cnum == numMarble) break;
}
count++;
}
if (s.size() > 0)
{
// 0에 대한 예외처리
if(s.top() != 0) groupList.push_back(make_pair(s.size(), s.top()));
while (!s.empty())
{
s.pop();
}
}
vector<int> eleList;
for (auto ele : groupList)
{
eleList.push_back(ele.first);
eleList.push_back(ele.second);
}
numMarble = min(N * N - 1, (int)eleList.size()); // 칸의 수보다 많아지지 못하도록
UpdateNewBoard(eleList);
}
int GetAnswer()
{
int ret = 0;
for (int i = 1; i <= 3; i++)
{
ret += (i * brokenMarble[i]);
}
return ret;
}
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
memset(board, 0, sizeof(board));
memset(brokenMarble, 0, sizeof(brokenMarble));
cin >> N >> M;
for (int row = 1; row <= N; row++)
{
for (int col = 1; col <= N; col++)
{
int num;
cin >> num;
board[row][col] = num;
if (num != 0) numMarble++;
}
}
for (int i = 0; i < M; i++)
{
int d, s;
cin >> d >> s;
spellList.push_back(make_pair(d, s));
}
sharkXpos = (N + 1) / 2;
sharkYpos = sharkXpos;
for (int i = 0; i < M; i++)
{
AttackIce(spellList[i].first, spellList[i].second);
MoveMarble();
while (ExploreMarble()) {};
UpdateMarbleGroup();
}
int ans = GetAnswer();
cout << ans << endl;
}
Leave a comment