백준(BOJ) 11559번 Puyo Puyo

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

11559번: Puyo Puyo

 

풀이 :

 

1.BFS를 통해 4 이상이 되는 모든 알파벳들은 v 배열에 담아주게 되고 '.'을 만든다.

 

2. 알파벳들을 밑으로 내리고 내릴 알파벳이 없다면 종료하고 있다면 1. 을 반복한다.

 

 

코드(C ++)

	#include <iostream>
	#include <algorithm>
	#include <vector>
	#include <queue>
	#include <cstring>
	using namespace std;
	char a[12][6];
	const int dy[4] = { 1,-1,0,0 };
	const int dx[4] = { 0,0,1,-1 };
	vector<pair<int, int>> v;
	int bfs(int y, int x, char alp) {
	int d[12][6];
	memset(d, -1, sizeof(d));
	queue<pair<int, int>> q;
	v.push_back({ y,x });
	q.push({ y,x });
	d[y][x] = 0;
	int cnt = 1;
	while (!q.empty()) {
	int y = q.front().first;
	int x = q.front().second;
	q.pop();
	for (int k = 0; k < 4; ++k) {
	int ny = y + dy[k];
	int nx = x + dx[k];
	if (!(0 <= ny && ny < 12 && 0 <= nx && nx < 6)) continue;
	if (a[ny][nx] != alp) continue;
	if (d[ny][nx] != -1) continue;
	v.push_back({ ny,nx });
	q.push({ ny,nx });
	d[ny][nx] = d[y][x] + 1;
	cnt += 1;
	}
	}
	return cnt;
	}
	int main() {
	for (int i = 0; i < 12; ++i)
	for (int j = 0; j < 6; ++j)
	cin >> a[i][j];
	int count = 0;
	while (1) {
	bool remov = false;
	for (int i = 11; i >= 0; --i) {
	for (int j = 0; j < 6; ++j) {
	if (a[i][j] == '.') continue;
	v.clear();
	if (bfs(i, j, a[i][j]) >= 4) {
	for (int z = 0; z < v.size(); ++z) {
	int y = v[z].first;
	int x = v[z].second;
	a[y][x] = '.';
	}
	remov = true;
	}
	}
	}
	if (remov) count++;
	bool stopCheck = false;
	// 모든 알파벳들을 밑으로 내린다
	for(int i=11; i >=0; --i)
	for (int j = 0; j < 6; ++j) {
	if (a[i][j] == '.') continue;
	int y = i, x = j;
	while (y < 11) {
	if (a[y + 1][x] == '.') {
	swap(a[y + 1][x], a[y][x]);
	stopCheck = true;
	y = y + 1;
	}
	else break;
	}
	}
	if (!stopCheck) break;
	}
	cout << count << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub