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

1.문제설명

......
......
......
......
......
......
......
......
.Y....
.YG...
RRYG..
RRYGG.

12 * 6 으로 Input이 주어질 때

같은 색깔인 칸이 상하좌우로 인접하여 4개 이상 있다면 모두 터트려줍니다.

......
......
......
......
......
......
......
......
.Y....
.YG...
..YG..
..YGG.

더이상 터질 수 있는 뿌요가 없다면

중력에 의해 공중에 있는 뿌요는 밑으로 떨어지게 됩니다.

......
......
......
......
......
......
......
......
......
..G...
.YYG..
.YYGG.

다시 터트리고 채워주고 반복하면서

터트리는 과정을 몇번 할 수 있는지 세면 되는 문제입니다.

2.접근방법[알고리즘]

이 문제는 시뮬레이션 문제로 두가지 과정을 구현해주면 됩니다.

1. 뿌요 터트리기

2. 뿌요 떨어트리기

뿌요 터트리기는 BFS를 돌면서 같은 뿌요가 있다면 몇개있는지 세주고 4개 이상 있다면

같은 뿌요들을 저장해준뒤 char '.'로 바꿔주면 쉽게 구현할 수 있습니다.

뿌요 떨어트리기는 for문을 돌면서 맨 아래칸부터 시작하여 위칸을 돌면서

뿌요가 있다면 뿌요가 없는 맨 아래칸과 바꿔주면 됩니다.

처음 주어지는 INPUT이 중력에 의해 떨어진 상태가 아닐수도 있기 때문에

맨 처음 뿌요를 일단 다 떨어트리고 시작해야합니다.

3.문제풀이코드 C++

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;

string arr[12];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

void fall() {
	for (int i = 0; i < 6; i++) {
		for (int j = 11; j >= 0; j--) {
			if (arr[j][i] == '.') {
				for (int k = j - 1; k >= 0; k--) {
					if (arr[k][i] != '.') {
						swap(arr[j][i], arr[k][i]);
						break;
					}
				}
			}
		}
	}
}


bool bomb() {
	bool ch[12][6];
	memset(ch, 0, sizeof(ch));
	queue<pair<int, int> > Q;
	bool bombed = false;

	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {

			if (ch[i][j] == 0 && arr[i][j] != '.') {

				vector<pair<int, int> > v;
				char color = arr[i][j];
				int cnt = 1;
				ch[i][j] = 1;
				v.push_back({ i,j });
				Q.push({ i,j });

				while (!Q.empty()) {
					int x = Q.front().first;
					int y = Q.front().second;
					Q.pop();


					for (int k = 0; k < 4; k++) {
						int nx = x + dx[k];
						int ny = y + dy[k];

						if (nx < 0 || nx >= 12 || ny < 0 || ny >= 6 || ch[nx][ny] == 1) continue;
						if (arr[nx][ny] == color) {
							cnt++;
							ch[nx][ny] = 1;
							Q.push({ nx,ny });
							v.push_back({ nx,ny });
						}
					}
				}

				if (cnt >= 4) {
					bombed = true;
					for (int k = 0; k < v.size(); k++) {
						arr[v[k].first][v[k].second] = '.';
					}
				}
			}
		}
	}

	return bombed;
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);


	for (int i = 0; i < 12; i++) {
		cin >> arr[i];
	}
	// 필드에 뿌요를 모두 두고 일단 떨어트린다. 
	fall();

	//1.터트린다 - 개수 0이면 끝
	//2. 내린다
	//1.2 반복
	int ans = 0;

	while (1) {
		if (bomb()) {
			ans++;
			fall();
		}
		else {
			break;
		}
	}

	cout << ans << '\n';

	return 0;
}