BOJ] 11559 Puyo Puyo(연세대학교 프로그래밍 경시대회 C번)

https://www.acmicpc.net/problem/11559

11559번: Puyo Puyo

입력

12*6의 문자가 주어진다.

이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다.

R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.(모두 대문자로 주어진다.)

입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태(즉 뿌요 아래에 빈 칸이 있는 경우는 없음) 이다.

출력

현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.)

 

 

문제 접근

간단한 BFS이고, 부숴지는 벽돌이 4개 이상 나오면 벽돌을 부수면서 보드판을 갱신해주면 된다. 이 과정에서 보드판 복사 과정이랑 그런 것들을 신경써야 하겠지만 문제의 제한 조건이 그렇게 까다롭지 않고, BFS 처리만 잘해주고 콤보 카운트만 진행하면 어렵지 않게 풀 수 있는 문제다. 아마 테트리스나 이런 보드 게임류를 직접 구현해본 사람이 있다면 손쉽게 해결할 수 있을 것이다.

 

 

 

소스코드

#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace  std;
int dir[4][2] =
{
	{1,0},{-1,0},{0,1},{0,-1}
};
const int R = 12, C = 6;

vector<vector<bool> > check;
vector<string> board;
vector<string> tmp;

bool isValid(int x, int y)
{
	return x >= 0 && x < C && y >= 0 && y < R;
}
void releaseBoard()
{
	for (int x = 0; x < C; x++)
	{
		queue<char> q;
		bool flag = false;
		int cnt = 0;
		for (int y = 0; y < R; y++)
		{
			if (tmp[y][x] != '.')
			{
				flag = true;
				q.push(tmp[y][x]);
			}
			if (flag && tmp[y][x] == '.')
				cnt++;
		}
		if (cnt)
		{
			int size = q.size();
			for (int y = 0; y < R - size; y++)
				tmp[y][x] = '.';
			for (int y = R - size; y < R; y++)
			{
				tmp[y][x] = q.front();
				q.pop();
			}
		}
	}
}
bool find(int y, int x)
{
	int cnt = 0;
	queue<pair<int, int> > q;
	vector<pair<int, int> > v;
	q.push(make_pair(y, x));
	check[y][x] = true;

	while (!q.empty())
	{
		int cy = q.front().first, cx = q.front().second;
		q.pop();
		cnt++;
		v.push_back(make_pair(cy, cx));

		for (int i = 0; i < 4; i++)
		{
			int ny = cy + dir[i][0], nx = cx + dir[i][1];
			if (isValid(nx, ny) && !check[ny][nx] && board[cy][cx] == board[ny][nx])
			{
				check[ny][nx] = true;
				q.push(make_pair(ny, nx));
			}
		}
	}

	if (cnt >= 4)
	{
		for (int i = 0; i < cnt; i++)
			tmp[v[i].first][v[i].second] = '.';
		releaseBoard();
		return true;
	}
	else
		return false;
}
int main(void)
{
	int ans = 0;

	board.resize(R);

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

	tmp = board;
	while (1)
	{
		check = vector<vector<bool> >(R, vector<bool>(C, false));
		int combo = 0;
		for (int y = 0; y < R; y++)
		{
			for (int x = 0; x < C; x++)
			{
				if (board[y][x] != '.' && !check[y][x])
				{
					bool broken = find(y, x);
					if (broken)
						combo++;
				}
			}
		}

		if (!combo)
			break;
		else
			ans++;

		board = tmp;
	}
	cout << ans;
}