[백준 11559] Puyo Puyo (C++)

1. 필드에 뿌요를 놓는다.

2. 뿌요는 아래로 떨어지기 때문에 아래에서부터 탐색하면 된다.

3. 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 터진다.

4. 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 한다.

 

---

 

C++)

#include <iostream>
#include <algorithm>
#include <queue>
#include <deque>
#define ROW_NUM 12
#define COL_NUM 6
using namespace std;

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

char arr[ROW_NUM][COL_NUM];			// 뿌요
bool visited[ROW_NUM][COL_NUM];		// 뿌요 방문
deque<pair<int, int>> puyo;			// 여러 뿌요 그룹이 동시에 터져야하기 떄문에 따로 보관

void PullDownPuyo() {
	queue<char> q;

	// 8. 중력의 영향을 받아 내려가는 뿌요들
	for (int j = 0; j < COL_NUM; j++) {
		for (int i = ROW_NUM - 1; i >= 0; i--) {
			if (arr[i][j] != '.') {
				q.push(arr[i][j]);
				arr[i][j] = '.';
			}
		}

		int i = ROW_NUM - 1;
		while (!q.empty()) {
			arr[i--][j] = q.front();
			q.pop();
		}
	}
}

void ErasePuyo() {
	while (!puyo.empty()) {
		int x = puyo.front().first;
		int y = puyo.front().second;
		arr[x][y] = '.';
		puyo.pop_front();
	}

	PullDownPuyo();
}

void FindSamePuyo(int i, int j) {
	int cnt = 0;
	
	// 5. 같은 색 뿌요를 찾는다.
	queue<pair<int, int>> q;
	q.push({ i,j });
	visited[i][j] = true;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		
		puyo.push_back({ x,y });	// 나중에 지울 뿌요
		cnt++;						// 뿌요 숫자 카운트
		
		q.pop();

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

			if (nx < 0 || nx >= ROW_NUM || ny < 0 || ny >= COL_NUM || visited[nx][ny])
				continue;

			if (arr[nx][ny] == arr[x][y] && !visited[nx][ny]) {
				q.push({ nx,ny });
				visited[nx][ny] = true;
			}
		}
	}

	// 6. 같은색 뿌요가 3개 이하면 못 터지므로 터트리려고 모아둔 뿌요 그룹에서 빼내준다.
	if (cnt < 4) {
		for (int i = 0; i < cnt; i++) {
			int x = puyo.back().first;
			int y = puyo.back().second;
			visited[x][y] = false;

			puyo.pop_back();
		}
	}
}

bool FindPuyo() {
	// 3. 뿌요는 아래부터 있으니까 아래서부터 탐색한다.
	for (int i = ROW_NUM - 1; i >= 0; i--) {
		for (int j = 0; j < COL_NUM; j++) {
			// 4. 색깔 뿌요 찾았으면 4개 이상 있는지 찾아본다.
			if (arr[i][j] != '.' && !visited[i][j]) {
				FindSamePuyo(i,j);
			}
		}
	}

	// 다음 뿌요 그룹을 찾아야하니까 일단 초기화
	for(int i = 0; i < ROW_NUM; i++)
			fill(visited[i], visited[i]+COL_NUM, false);
		
	//  7. 터질 뿌요가 있다.
	if (!puyo.empty()) {
		ErasePuyo();
		return true;
	}

	// 9. 터질 뿌요 없다. -> 탐색 종료
	return false;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	// 1. 필드에 뿌요를 놓는다.
	for (int i = 0; i < ROW_NUM; i++) {
		for (int j = 0; j < COL_NUM; j++)
			cin >> arr[i][j];
	}

	int ans = 0;
	// 2. 터질 뿌요 그룹을 찾는다.
	while(FindPuyo())
		ans += 1;

	cout << ans;

	return 0;
}

 

프로그래머스에 비슷한 문제가 있었던 것 같은데 문제 이름이 기억이 안난다...