[C++] 백준 문제풀이 (Simulation) 11559번 Puyo Puyo

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

11559번: Puyo Puyo

 

 

 

 

 

#include <bits/stdc++.h>



const int h = 12;
const int w = 6;
std::string field[h];
bool visit[h][w];
int ans;
const int dy[] = {-1, 1, 0, 0};
const int dx[] = {0, 0, -1, 1};
std::vector<std::pair<int, int>> save;
bool boom;


void bfs(int i, int j, char type) {

	std::queue<std::pair<int, int>> q;
	visit[i][j] = true;
	save.push_back({i, j});
	q.push({i, j});

	while(!q.empty()) {
		auto [y, x] = q.front(); q.pop();
		for (int dir = 0; dir < 4; ++dir) {
			int ny = y + dy[dir];
			int nx = x + dx[dir];
			if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
			if (visit[ny][nx]) continue;
			if (field[ny][nx] != type) continue;

			visit[ny][nx] = true;
			save.push_back({ny, nx});
			q.push({ny, nx});
		}
	}

	if (save.size() >= 4) {
		boom = true;
		for (auto p : save) {
			field[p.first][p.second] = '.';
		}
	}
	save.clear();
}


void update(int x){ 
	for (int y = h - 1; y >= 0; --y) {
		if (field[y][x] == '.') continue;
		int sy = y + 1;
		while(sy < h && field[sy][x] == '.') {
			field[sy][x] = field[sy - 1][x];
			field[sy - 1][x] = '.';
			++sy;
		}
	}
}



int main(int argc, char** argv) {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	for (int i = 0; i < h; ++i){
		std::cin >> field[i];
	}

	do {
		boom = false;
		// 하단부터 시작해서 bfs탐색 후 4개이상 모였으면 제거
		for (int y = h - 1; y >= 0; --y) {
			for (int x = 0; x < w; ++x) {
				if (field[y][x] == '.') continue;
				bfs(y, x, field[y][x]);
			}
		}
		if (!boom) break;
		// 뿌요뿌요를 아래로 밀착
		for (int x = 0; x < w; ++x){
			update(x);
		}

		++ans;

		for (int y = 0; y < h; ++y){
			std::fill(visit[y], visit[y] + w, false);
		}

	} while(true);

	std::cout << ans << "\n";

	return 0;
}