백준 11559번 Puyo Puyo C++

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

 

bfs로 같은 색이 4개이상 이어져있으면 그 부분을 터트려서 빈 공간으로 만들고 다 터지면 밑에서부터 탐색하면서 밑에 빈 공간이 있으면 밑으로 내려오도록 했다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

const int ROW = 12;
const int COL = 6;

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

vector<vector<char>> board(ROW, vector<char>(COL));
vector<vector<bool>> found(ROW, vector<bool>(COL, false));

void RefreshFound() {
	for (int i = 0; i < ROW; i++) {
		for (int j = 0; j < COL; j++) {
			found[i][j] = false;
		}
	}
}

bool BFS(int row, int col) {
	char target = board[row][col];
	int cnt = 0;
	vector<pair<int, int>> v;
	queue<pair<int, int>> q;
	q.push({ row,col });
	found[row][col] = true;
	while (!q.empty()) {
		cnt++;
		auto curr = q.front();
		v.push_back(curr);
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nextRow = curr.first + dRow[i];
			int nextCol = curr.second + dCol[i];
			if (nextRow >= ROW || nextRow < 0) continue;
			if (nextCol >= COL || nextCol < 0) continue;
			if (board[nextRow][nextCol] != target) continue;
			if (found[nextRow][nextCol]) continue;
			found[nextRow][nextCol] = true;
			q.push({ nextRow,nextCol });
		}
	}
	if (cnt >= 4) {
		for (auto a : v) {
			board[a.first][a.second] = '.';
		}
		return true;
	}
	return false;
}

void GoDown(int row, int col) {
	int nextRow = row;
	while (true) {
		if (nextRow + 1 >= ROW) break;
		if (board[nextRow + 1][col] != '.') break;
		nextRow++;
	}
	if (row == nextRow) return;
	board[nextRow][col] = board[row][col];
	board[row][col] = '.';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	for (int i = 0; i < ROW; i++) {
		for (int j = 0; j < COL; j++) {
			cin >> board[i][j];
		}
	}
	int ans = 0;
	while (true) {
		bool changed = false;

		for (int i = 0; i < ROW; i++) {
			for (int j = 0; j < COL; j++) {
				if (board[i][j] == '.') continue;
				bool boom = BFS(i, j);
				changed |= boom;
			}
		}

		for (int i = ROW - 1; i >= 0; i--) {
			for (int j = 0; j < COL; j++) {
				if (board[i][j] == '.') continue;
				GoDown(i, j);
			}
		}

		RefreshFound();

		if (!changed) break;

		ans++;
	}
	cout << ans;
};