백준 11559 - Puyo Puyo

문제링크

• 백준 11559

문제설명

• 12 x 6 크기의 게임판에 빈칸(‘.’), 색깔(‘R’, ‘G’, ‘B’, ‘P’, ‘Y’)이 놓여 있다.
• 상하좌우로 같은 색깔이 4개 이상 연결된 영역은 터진다. 터질 수 있는 그룹이 여러 개라면 동시에 터져야하고, 연쇄는 한번만 카운트 된다.
• 뿌요가 터지고 나면 중력에 의해 위쪽에 존재하던 뿌요들이 게임판의 아래쪽으로 쭉 내려온다.
• 연쇄가 몇 번 연속으로 일어나는지 구하라.

문제접근

• 게임판에서 색깔이 칠해진 칸은 BFS를 통해 몇개의 칸이 그룹을 이루는지 찾는다.
  • 4개 이상의 칸이 그룹을 이룬다면, 뿌요가 터진다.
• 터질 수 있는 그룹이 모두 터지고 나면 연쇄를 1 추가하고, 위에 존재하는 색깔 칸들을 게임판의 아래로 내린다.
• 터진 그룹이 하나도 없다면 로직을 종료한다.

구현

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <memory.h>
using namespace std;

vector<string> board;
bool visited[12][6];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int ans = 0;

void popPuyo(int x, int y, bool& flag) {
	int cnt = 1;
	char curColor = board[x][y];
	vector<string> nboard = board;
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visited[x][y] = true;
	nboard[x][y] = '.';


	while (!q.empty()) {
		pair<int, int> cpos = q.front();
		q.pop();
		
		for (int dir = 0; dir < 4; dir++) {
			int nextX = cpos.first + dx[dir];
			int nextY = cpos.second + dy[dir];
			if (nextX < 0 || nextX >= 12 || nextY < 0 || nextY >= 6) continue;
			if (board[nextX][nextY] != curColor) continue;
			if (visited[nextX][nextY]) continue;
			visited[nextX][nextY] = true;
			q.push(make_pair(nextX, nextY));
			nboard[nextX][nextY] = '.';
			cnt++;
		}
	}

	if (cnt >= 4) {
		flag = true;
		board = nboard;
	}
}

void setGravity() {
	int idx = 11;
	for (int c = 0; c < 6; c++) {
		idx = 11;
		for (int r = 11; r >= 0; r--) {
			if (board[r][c] != '.') {
				if (r == idx) {
					idx--;
					continue;
				}
				board[idx--][c] = board[r][c];
				board[r][c] = '.';
			}
		}
	}
}

bool playPuyo() {
	bool flag = false;
	memset(visited, false, sizeof(visited));
	for (int r = 0; r < 12; r++) {
		for (int c = 0; c < 6; c++) {
			if (board[r][c] == '.') continue;
			if (visited[r][c]) continue;
			popPuyo(r, c, flag);
		}
	}
	if (flag == false) return false;
	
	ans++;
	setGravity();
	return true;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	string line;
	for (int i = 0; i < 12; i++) {
		cin >> line;
		board.push_back(line);
	}

	while (true) {
		if (playPuyo() == false) break;
	}
	printf("%d\n", ans);
	return 0;
}