[C++] 백준 11559번 - Puyo Puyo

실제 뿌요뿌요 게임을 구현하는 문제였다.

아이디어는 이렇다 4개 이상의 같은 색깔의 슬라임(?)이 모이면 터지고 1연쇄가 일어난 후 뿌요들이 아래로 중력에 의해 내려온다. 이 문제를 풀때 간과했던 것은 한 번에 터뜨릴 수 있는 것들은 한번에 터지고 이는 1 연쇄이다. 그래서 한번에 2개의 그룹이 터져도 2연쇄가 아니라 1연쇄이다. 이 부분을 제외하면 재밌게 풀었던 문제이다. 

 

#include <bits/stdc++.h>
#include <cstring>
#define endl '\n'
using namespace std;

char graph[12][6];
bool visited[12][6];
const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };
int ans = 0;
//일반 bfs
int bfs(int x, int y, bool flag) {
	char target = graph[x][y];
	queue<pair<int, int>> q;
	queue<pair<int, int>> change; //만약 flag == true일때 방문한 점을 다시 '.'로 만들어 주기 위한 작업
	change.push({ x, y });
	q.push({ x, y });
	visited[x][y] = true;
	int connected = 1;
	while (!q.empty()) {
		auto curr = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = curr.first + dx[i];
			int ny = curr.second + dy[i];
			if (nx < 0 || ny < 0 || nx >= 12 || ny >= 6) continue;
			if (graph[nx][ny] != target) continue;
			if (visited[nx][ny]) continue;
			q.push({ nx, ny });
			change.push({ nx, ny });
			visited[nx][ny] = true;
			connected++;
		}
	}

	if (flag) {
		while (!change.empty()) {
			auto cur = change.front();
			graph[cur.first][cur.second] = '.';
			change.pop();
		}
	}
	return connected;
}

//연쇄가 일어난다면 칸을 .로 채우기
int blast() {
	memset(visited, false, sizeof(visited));
	bool flag = false;
	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {
			if (graph[i][j] != '.' && !visited[i][j]) {
				if (bfs(i, j, false) >= 4) {
					flag = true;
					memset(visited, false, sizeof(visited));
					bfs(i, j, true);
					//break;
				}
			}
		}
		//if (flag) break;
	}
	if (flag) return 1;
	else return 0;
}
//중력에 의해 아래로 이끌려 내려오기
void pullDown() {
	for (int j = 0; j < 6; j++) {
		for (int i = 11; i >= 0; i--) {
			if (graph[i][j] != '.') {
				for (int o = i; i + 1 < 12 && graph[o + 1][j] == '.'; o++) {
					char temp = graph[o][j];
					graph[o][j] = graph[o + 1][j];
					graph[o + 1][j] = temp;
				}
			}
		}
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {
			cin >> graph[i][j];
		}
	}

	while (blast()) {
		pullDown();
		ans += 1;
	}

	//for (int i = 0; i < 12; i++) {
	//	for (int j = 0; j < 6; j++) {
	//		cout <<  graph[i][j];
	//	}
	//	cout << endl;
	//}

	cout << ans << endl;

	return 0;
}