[C++]백준 11559 - Puyo Puyo

11559번: Puyo Puyo

 

풀이

---

딱히 어렵진 않았는데 문제 해석을 잘못해서 뿌요뿌요 플레이 영상보면서 고치느라 시간이 조금 걸렸다.

 

아래쪽부터 탐색을 시작해서 해당 주변에 같은 타일이 있다면 큐와 region 벡터에 담고 그 타일을 탐색한다.

더이상 주변에 같은 타일이 없을 경우 region 벡터의 사이즈가 4이상 이라면 region의 요소들을 초기화하고 해당 칸을 빈칸으로 한다. 만약 사이즈가 3 이하면은 그냥 초기화만 한다.

 

이런식으로 한번 모든 타일을 쭉 탐색한 뒤 만약 사이즈가 4이상이였던 region이 한번이라도 있으면 위의  과정을 다시 시작한다.

코드

---

 

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
char map[13][13];
int flag[13][13];

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0, -1,0,1 };
int puyo = 0;
void PuyoPuyo() {
	queue<pair<int, int>> queue;
	vector<pair<int, int>> region;
	bool find = false;
	for (int y = 0; y < 12; y++) {
		for (int x = 0; x < 6; x++) {
			if (map[y][x] == '.')
				continue;
			queue.push(make_pair(x, y));

			while (!queue.empty()) {
				int queueX = queue.front().first;
				int queueY = queue.front().second;
				region.push_back(make_pair(queueX, queueY));
				flag[queueY][queueX] = 1;

				queue.pop();
				for (int i = 0; i < 4; i++) {
					int searchX = queueX + dx[i];
					int searchY = queueY + dy[i];
					if (map[searchY][searchX] == '.')
						continue;

					if (map[searchY][searchX] == map[queueY][queueX] && flag[searchY][searchX] == 0) {
						queue.push(make_pair(searchX, searchY));
					}
				}
			}
			if (region.size() >= 4) {
				if(!find)
				puyo++;
				find = true;
				for (int i = 0; i < region.size(); i++) {
					int regionX = region[i].first;
					int regionY = region[i].second;
					flag[regionY][regionX] = 0;
					map[regionY][regionX] = '.';
				}
			}
			else {
				for (int i = 0; i < region.size(); i++) {
					int regionX = region[i].first;
					int regionY = region[i].second;
					flag[regionY][regionX] = 0;
				}
			}
			region.clear();
		}
	}
	if (find) {
		for (int x = 0; x < 6; x++) {
			for (int y = 0; y < 12; y++) {
				if (map[y][x] != '.') {
					for (int downY = y - 1; downY >= 0; downY--) {
						char tile = map[y][x];
						if (map[downY][x] != '.') {
							map[y][x] = '.';
							map[downY + 1][x] = tile;
							break;
						}
						if (downY == 0) {
							map[y][x] = '.';
							map[0][x] = tile;
						}
					}
				}
			}
		}
		PuyoPuyo();
	}
}
bool InMap(int x, int y) {
	if (0 <= x && x < 6 && 0 <= y && y < 12)
		return true;
	return false;
}

int main() {
	for (int y = 11; y >= 0; y--) {
		string line;
		cin >> line;
		for (int x = 0; x < 6; x++) {
			map[y][x] = line[x];
			flag[y][x] = 0;
		}
	}
	PuyoPuyo();
	cout << puyo << endl;
}