(BOJ) 11559 Puyo Puyo

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

 

 

문제 풀이:

1. 터질 수 있는 뿌여 그룹 찾기 -> '.'이 아닌 점에서 bfs 돌려서 4개 이상 이어져 있으면 vector에 push

2. 현재 모양에서 터질 수 있는 뿌여 그룹을 다 찾았으면 각 그룹을 없애고 위에 것들을 끌어 내림

   ㄴ> 위에서부터 작업할 수 있도록 정렬해주고 작업

3. 터뜨리고 res++   -> 한 번에 여러 그룹 터뜨리면 res는 한 번만 ++됨.

 

소스 코드:

typedef pair<int, int> P;
int res;
int dx[4] = { 0,1,-1,0 };
int dy[4] = { 1,0,0,-1 };
bool visit[12][6];
char arr[12][6];
vector<vector<P>> bomb;

void bfs(int x, int y);
void func() {
	
	memset(visit, false, sizeof(visit));
	bomb.clear();
	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {
			if (!visit[i][j] && arr[i][j] != '.') {
				bfs(i, j);
			}
		}
	}
	if (bomb.empty()) return;
	
	for (int j = 0; j < bomb.size(); j++) {
		sort(bomb[j].begin(), bomb[j].end());
		for (int i = 0; i < bomb[j].size(); i++) {
			int x = bomb[j][i].first;
			int y = bomb[j][i].second;
			for (int k = x; k > 0;k--) {
				arr[k][y] = arr[k - 1][y];
			}
			arr[0][y] = '.';
		}
	}
	res++;
	func();
}
void bfs(int x,int y) {

	char c = arr[x][y];
	queue<P> q;
	vector<P> v;
	visit[x][y] = true;
	v.push_back({x,y});
	q.push({ x,y });
	while (!q.empty()) {
		int x1 = q.front().first;
		int y1 = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int xx = x1 + dx[i];
			int yy = y1 + dy[i];
			if (xx < 0 || xx == 12 || yy < 0 || yy == 6 || visit[xx][yy] || arr[xx][yy] != c) continue;
			visit[xx][yy] = true;
			q.push({ xx,yy });
			v.push_back({ xx,yy });
		}
	}
	if (v.size() >= 4) bomb.push_back(v);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {
			cin >> arr[i][j];
		}
	}
	func();
	cout << res << '\n';
	return 0;
}