728x90
문제
https://www.acmicpc.net/problem/11559
풀이 방법
예전에 유명했던 테트리스 비슷한 게임인 뿌요뿌요 관련된 문제이다. 뿌요뿌요는 같은 색깔이 4개 이상 연결되어 있으면 터지며, 터진 후에 위에 있던 뿌요들이 아래로 내려오면서 연결되면 또 터진다. 이를 연쇄라고 한다.
필드의 정보가 주어졌을때 연쇄가 얼마나 일어나는지 계산하는 문제이다.
- 4개 이상 연결되어 있는 뿌요를 찾는다.
- 터뜨린다. (빈 칸으로 만든다)
- 위에 있던 뿌요들을 아래로 내린다.
가 몇 번 반복되는지 계산하면 된다. 아래 코드에서는 1과 2를 하나의 PopPuyo
함수로, 3을 Collapse
함수로 만들었다.
연결되어있는 뿌요를 찾는 것은 BFS를 사용하면 쉽게 판별할 수 있다. 하지만 아래로 내리는 로직이 생각해내기가 좀 어렵다. 왜냐하면 다음과 같은 케이스들이 있기 때문이다.
- 뿌요 - 빈칸 - 뿌요
- 빈칸 - 뿌요
- 뿌요 - 빈칸
뿌요와 빈 칸 인덱스를 일일이 찾아서 처리해주기가 번거로울 것 같아 그냥 큐에 담아서 담아진대로 일렬로 배치하는 방식을 사용했다.
코드
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int dy[] = {-1,0,0,1};
int dx[] = {0,-1,1,0};
bool PopPuyo(vector<vector<char>>& field)
{
bool popped = false;
vector<vector<bool>> visited(12, vector<bool>(6, false));
queue<pair<int, int>> q;
for(int i=11; i>=0; i--)
{
for(int j=0; j<6; j++)
{
// 같은 색 뿌요 연결
if(!visited[i][j] && field[i][j] != '.')
{
vector<pair<int, int>> puyo;
char color = field[i][j];
q.push({i,j});
visited[i][j] = true;
puyo.push_back({i,j});
while(!q.empty())
{
auto cur = q.front();
q.pop();
int y = cur.first;
int x = cur.second;
for(int k=0; k<4; k++)
{
int ny = y+dy[k];
int nx = x+dx[k];
if(ny < 0 || ny >= 12 || nx < 0 || nx >= 6) continue;
if(field[ny][nx] != color || visited[ny][nx]) continue;
q.push({ny,nx});
visited[ny][nx] = true;
puyo.push_back({ny,nx});
}
}
// 연결된 뿌요가 4개이상이면 터뜨림
if(puyo.size() >= 4)
{
popped = true;
for(const auto& t : puyo)
{
int y = t.first;
int x = t.second;
field[y][x] = '.';
}
}
}
}
}
return popped;
}
void Collapse(vector<vector<char>>& field)
{
for(int i=0; i<6; i++)
{
queue<char> q;
for(int j=11; j>=0; j--)
{
if(field[j][i] != '.') q.push(field[j][i]);
}
for(int j=11; j>=0; j--)
{
if(q.empty()) field[j][i] = '.';
else
{
field[j][i] = q.front();
q.pop();
}
}
}
}
int main()
{
vector<vector<char>> field(12, vector<char>(6));
for(int i=0; i<12; i++)
{
for(int j=0; j<6; j++)
{
scanf(" %1c", &field[i][j]);
}
}
int answer = 0;
while(PopPuyo(field))
{
Collapse(field);
answer++;
}
printf("%d", answer);
return 0;
}
고찰
연결되어 있는 뿌요가 몇 번 터지는지 계산하는 문제인줄 알고 삽질했었다. 문제를 잘 읽자...
비슷한 문제로는 https://www.acmicpc.net/problem/12100 가 있다.
뿌요뿌요를 풀었다면 이 문제도 풀 수 있을 것이다.
여담으로 테트리스는 유명한데 뿌요뿌요는 그렇지 않은 것 같다.
둘 다 고인물 게임이면서 뭔가 쌓아놓고 터뜨린다는 공통점이 있어서 그런지 콜라보한 게임도 있다.
심심하거나 머리 식히는 용으로 한번 봐보자!
728x90