BOJ 11559 - Puyo Puyo
“BFS를 이용한 시뮬레이션”
BOJ 11559 - Puyo Puyo
문제 링크
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f;
using namespace std;
string board[15];
vector<pair<int,int>>coor;
queue<pair<int,int>>q;
int vis[15][15];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int arr[128];
int ans;
int getCoor()
{
for (int i = 0; i < 12; i++)
fill(vis[i], vis[i]+6, 0);
char curC;
for (int i = 0; i < 12; i++) {
for (int j = 0; j < board[i].length(); j++) {
if (board[i][j] != '.' && !vis[i][j]) {
curC = (char) board[i][j];
if (arr[curC] == 0)
coor.push_back({i, j});
arr[curC]++;
vis[i][j] = 1;
q.push({i, j});
while (!q.empty()) {
pair<int,int>cur = q.front(); q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if (nx < 0 || nx > 11 || ny < 0 || ny > 6)
continue ;
if ((char)board[nx][ny] != curC || vis[nx][ny])
continue;
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
arr[curC] = 0;
}
}
if (coor.empty())
return 0;
return 1;
}
void falldown()
{
for (int j = 0; j < 6; j++) {
int pos = 0;
int fixed = 0;
for (int i = 0; i < 12; i++) {
if (board[i][j] == '.' && !fixed) {
pos = i; fixed = 1;
}
else if (board[i][j] != '.' && fixed == 1) {
char c = board[i][j];
int temp = i;
board[pos][j] = c;
board[i][j] = '.';
i = pos;
fixed = 0;
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); std::cout.tie(NULL);
for (int i = 11; i >= 0; i--) {
string s; cin >> s;
board[i] = s;
}
while (getCoor() == 1)
{
bool isBroken = false;
for (int i = 0; i < 12; i++)
fill(vis[i], vis[i]+6, 0);
int point;
char curC;
vector<pair<int,int>>toErase;
for (int i = 0; i < coor.size(); i++) {
pair<int,int>cur = make_pair(coor[i].first, coor[i].second);
q.push({cur.first, cur.second});
curC = board[coor[i].first][coor[i].second];
vis[coor[i].first][coor[i].second] = 1;
point = 1;
while (!q.empty()) {
pair<int,int>curP = q.front(); q.pop();
toErase.push_back({curP.first, curP.second});
for (int dir = 0; dir < 4; dir++) {
int nx = curP.first + dx[dir];
int ny = curP.second + dy[dir];
if (nx < 0 || nx > 11 || ny < 0 || ny > 6)
continue;
if ((char)board[nx][ny] != curC || vis[nx][ny])
continue;
toErase.push_back({nx, ny});
point++;
vis[nx][ny] = 1;
q.push({nx,ny});
}
}
if (point >= 4) {
isBroken = true;
for (int i = 0; i < toErase.size(); i++)
board[toErase[i].first][toErase[i].second] = '.';
}
toErase.clear();
}
falldown();
if (isBroken)
ans++;
else
break ;
coor.clear();
}
cout << ans;
return 0;
}
- 시뮬레이션 문제는 거의 풀어본 적이 없는데, 이 정도로 풀이가 길게 뽑힐 줄은 몰랐다. 코드의 진행 자체는 간단한 편으로, BFS로 보드를 순회하면서 하나의 색깔로 이루어진, 상하좌우로 이어진 영역의 시작점 좌표를 전부 구한 뒤, 다시 한번 BFS를 돌아 영역이 4개 이상이라면 전부 ‘.’으로 바꾸고, 중력의 영향을 받은 보드를 새로 그려주며, 연쇄가 발생해 보드가 바뀌었다면 위의 과정을 처음부터 반복하고 연쇄가 발생하지 않았다면 반복문을 탈출해 여태까지 연쇄가 발생한 횟수를 출력하는 것이다.
// vector에 영역의 좌표를 하나씩만 기록한다.
int getCoor()
{
for (int i = 0; i < 12; i++)
fill(vis[i], vis[i]+6, 0);
char curC;
for (int i = 0; i < 12; i++) {
for (int j = 0; j < board[i].length(); j++) {
if (board[i][j] != '.' && !vis[i][j]) {
curC = (char) board[i][j];
// coor에는 영역의 좌표가 하나만 필요하기 때문에
// (arr[curC] == 0) 조건을 넣어 단 한번만 좌표를 기록했다.
if (arr[curC] == 0)
coor.push_back({i, j});
// arr[curC]++로 인해 이제 좌표가 한번 기록된 이후에는 다시 기록되지 않는다.
arr[curC]++;
vis[i][j] = 1;
q.push({i, j});
while (!q.empty()) {
pair<int,int>cur = q.front(); q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if (nx < 0 || nx > 11 || ny < 0 || ny > 6)
continue ;
// board[nx][ny] 조건에 문자열 조건이 추가되었다.
if ((char)board[nx][ny] != curC || vis[nx][ny])
continue;
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
arr[curC] = 0;
}
}
if (coor.empty())
return 0;
return 1;
}
- BFS는 문제가 하도 많아서, 기본 틀만 외워두면 문제에 따라 무한으로 변형 가능한 것이 매력인 것 같다. 현재의 문자열이 무엇인지 저장하는 변수를 하나 만들어서, continue 조건에 문자열의 일치 여부를 포함시켰다. 또한 영역의 좌표를 하나라도 구해 vector에 추가했으면 그 영역을 순회하되, 좌표를 vector에 추가시키면 안되기 때문에 그 조건도 추가했다. 함수 개시시에 단 하나의 영역이라도 존재하면 vector에 좌표가 추가되고, 1을 반환하며 그렇지 않고 전부 ‘.’ 이라면 0을 반환하여 메인 while문을 탈출하게 된다.
for (int i = 0; i < coor.size(); i++)
{
pair<int,int>cur = make_pair(coor[i].first, coor[i].second);
q.push({cur.first, cur.second});
curC = board[coor[i].first][coor[i].second];
vis[coor[i].first][coor[i].second] = 1;
point = 1;
while (!q.empty()) {
pair<int,int>curP = q.front(); q.pop();
toErase.push_back({curP.first, curP.second});
for (int dir = 0; dir < 4; dir++) {
int nx = curP.first + dx[dir];
int ny = curP.second + dy[dir];
if (nx < 0 || nx > 11 || ny < 0 || ny > 6)
continue;
if ((char)board[nx][ny] != curC || vis[nx][ny])
continue;
toErase.push_back({nx, ny});
point++;
vis[nx][ny] = 1;
q.push({nx,ny});
}
}
if (point >= 4) {
isBroken = true;
for (int i = 0; i < toErase.size(); i++)
board[toErase[i].first][toErase[i].second] = '.';
}
toErase.clear();
}
그렇게 구한 영역의 좌표로 이루어진 vector를 순회하며 그 영역의 크기를 구하면서 영역의 구역 하나하나의 좌표를 기록하고, 영역의 크기가 4 이상이라면 미리 기록해둔 좌표를 순회하며 해당 값을 ‘.’로 바꾸고 그렇지 않다면 넘어간다. BFS 자체는 위의
getCoor()함수와 거의 비슷하지만 영역의 크기를 재는 로직이 추가되었다.미리 파괴가 발생했는지, 아닌지를 기록할
bool isBroken을 false로 선언하여 한번이라도 point가 4 이상이어서 파괴가 발생했을 때, 이를 true로 바꿔준다. isBroken이 false라면 연쇄가 끝난 것이므로 반복문을 탈출하면 될 것이다.
void falldown()
{
for (int j = 0; j < 6; j++) {
int pos = 0;
int fixed = 0;
for (int i = 0; i < 12; i++) {
if (board[i][j] == '.' && !fixed) {
pos = i; fixed = 1;
}
else if (board[i][j] != '.' && fixed == 1) {
char c = board[i][j];
int temp = i;
board[pos][j] = c;
board[i][j] = '.';
i = pos;
fixed = 0;
}
}
}
}
- 크기가 4 이상인 영역들이 파괴되어 빈 공간이 생기고, 중력에 따라 블럭이 내려오는 것을 구현하는 함수이다. 쉬워보였는데 생각보다 구현하기가 까다로웠다. for문을 돌 때, i 값을 직접 조작할 수 있다는 점을 이용하여 ‘.’ 가 위치한 값을 고정시켜두고, 점 이외에 다른 문자열이 나왔을 때 문자열의 인덱스와 ‘.’의 인덱스를 바꾼 이후, i를 원래 ‘.’이 있었던 이전의 위치로 후퇴시켜 거기서부터 다시 for문을 돌도록 만들었다. 이러면 문자열을 만날 때마다, 이전에 기록해두었던 점의 위치로 움직이게 만들어줄 수가 있다.
else if (board[i][j] != '.' && fixed == 1)이 조건도 중요한데,fixed == 1조건을 빠트리면 안된다. 저 조건이 빠지면 fixed가 0일 때마다 계속 저 분기로 들어가게 된다.
// ... implementation
falldown();
if (isBroken)
ans++;
else
break ;
coor.clear();
}
cout << ans;
return 0;
}
- 이후 미리 만들어준 isBroken이 true라면 연쇄의 횟수를 하나 더하고, 그렇지 않다면 while 문을 탈출한다. 다 사용한 좌표의 vector는 비워준다.
