[BOJ] 11559 : Puyo Puyo

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

---

시뮬레이션 BFS

 Puyo Puyo 게임을 구현하는 문제로 시뮬레이션입니다.

1)

 현재 Map 상태에서 BFS 탐색을 통해 4개 이상 상하좌우로 연결되어있는 블록들을 모두 체크한다. 이때, Map의 모든 지점에서 블록이 있다면 BFS 탐색을 진행하고, BFS 탐색을 진행하는 동안 이동하는 경로를 다 저장한다. 경로가 4개 이상이면(4개 이상 연결된 블록이 있다면) 해당 블록들을 따로 체크해둔다.

2)

 1)에서 4개 이상 연결된 블록이 없었다면 게임을 끝낸다.

3)

현재 Map 상태에서 블록들을 아래로 이동시켜준다.

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

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

	int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
	char map[12][7] = {};
	for (int i = 0; i < 12; i++)
		cin >> map[i];
	
	int cnt = 0;
	while (1) {
		// 터뜨릴 수 있는 모든 뿌요를 터뜨리자.
		bool isFinished = false;
		bool isBomb[12][6] = {};
		for (int i = 11; i >= 0; i--) {
			for (int j = 0; j < 6; j++) {
				if (map[i][j] != '.' && isBomb[i][j] == false) {
					// 스팟마다 BFS 탐색을 진행하면서 경로 저장.
					queue<pair<int, int>> q;
					vector<pair<int, int>> temp;
					q.push({ i, j });
					isBomb[i][j] = true;
					temp.push_back({ i, j });
					while (!q.empty()) {
						int curX = q.front().first, curY = q.front().second;
						q.pop();
						for (int k = 0; k < 4; k++) {
							int nX = curX + dx[k], nY = curY + dy[k];
							if (!(0 <= nX && nX < 12 && 0 <= nY && nY < 6)) continue;
							if (map[nX][nY] != map[curX][curY]) continue;
							if (isBomb[nX][nY]) continue;
							q.push({ nX, nY });
							temp.push_back({ nX, nY });
							isBomb[nX][nY] = true;
						}
					}
					if (temp.size() >= 4) {
						isFinished = true;
					}
					else { // 지금 탐색한 경로는 4개 이상의 블록 X
						for (int k = 0; k < temp.size(); k++) {
							isBomb[temp[k].first][temp[k].second] = false;
						}
					}
				}
			}
		}
		// 터뜨릴 수 있는 뿌요가 없다면 break;
		if (!isFinished) break;
		// 먼저 터진 부분 처리!
		for (int i = 0; i < 12; i++)
			for (int j = 0; j < 6; j++)
				if (isBomb[i][j]) map[i][j] = '.'; 
		// 맵을 이동하자.
		for (int j = 0; j < 6; j++) {
			for (int k = 0; k < 11; k++) { // 각 열마다 12번씩 행을 아래로 끌어내리자.
				for (int i = 10; i >= 0; i--) {
					if (map[i][j] != '.') {
                    	int l = i + 1;
						if (map[l][j] != '.') continue;
						while (l < 12 && map[l][j] == '.')
							l++;
						map[l - 1][j] = map[i][j];
						map[i][j] = '.';
					}
				}
			}
		}
		cnt++;
	}
	cout << cnt << '\n';
	return 0;
}

---