[백준 11559] 뿌요뿌요

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

11559번: Puyo Puyo

#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
char board[12 + 2][6 + 2];

struct _st
{
	int x, y;
};
std::vector<_st> V;

std::queue<_st> Q;
int visited[12 + 2][6 + 2];


void input()
{
	for (int i = 0; i < 12; i++) {
		scanf("%s", &board[i]);
	}
}


void BFS(int x, int y, char color)
{
	// init
	Q = {};
	V.clear();
	
	// dir
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	Q.push({ x, y });
	visited[x][y] = 1;
	V.push_back({ x, y });

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > 12 - 1 || ny < 0 || ny > 6 - 1) continue;
			if (visited[nx][ny]) continue;
			if (board[nx][ny] == '.' || board[nx][ny] != color) continue;
			Q.push({ nx, ny });
			visited[nx][ny] = 1;
			V.push_back({ nx, ny });
		}
	}
}



bool Flood_Fill()
{
	memset(visited, 0, sizeof(visited));

	bool crush = false;

	for (int i = 12 - 1; i >= 0; i--) {
		for (int j = 0; j < 6; j++) {
			if (board[i][j] == '.') continue;
			if (visited[i][j]) continue;
			BFS(i, j, board[i][j]);
			if (V.size() >= 4) {
				for (_st v : V) { 
					board[v.x][v.y] = '.';
				}
				crush = true;
			}
		}
	}
	return crush;
}


void gravity()
{
	std::queue<char> P;

	for (int j = 0; j < 6; j++) {
		for (int i = 12 - 1; i >= 0; i--) {
			if (board[i][j] == '.') continue;
			P.push(board[i][j]);
			board[i][j] = '.';
		}
		int row = 12 - 1;
		while (!P.empty()) {
			board[row][j] = P.front();
			P.pop();
			row--;
		}
	}
}


int puyo_puyo()	// simulation
{
	int combo = 0;
	while (1) {
		if (!Flood_Fill()) return combo;
		gravity();
		combo++;
	}
}



int main()
{
	input();
	int ans = puyo_puyo();
	printf("%d\n", ans);
	return 0;
}

"뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. "

=> 주어진 시작점으로부터 연결된 영역들을 찾는 알고리즘 : Flood-Fill

 

사실 별 다를건 없지만... 그래도 다시 푼 게 좀 더 깔끔해서 갱신해본다. 

더이상 뿌요그룹 안생길 때 까지 플루드 필 + 연쇄작용 일어나지 않을 때 까지 플루드 필

 

---

이전에 구현했던 코드 및 설명..

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
char board[12 + 2][6 + 2];
int visited[12 + 2][6 + 2];


struct _st
{
	int x;
	int y;
};

void input()
{
	for (int i = 0; i < 12; i++) {
		scanf("%s", &board[i]);
	}
}


bool BFS(int type, int x, int y)
{
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);	// 방문배열 초기화 

	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };
	
	std::queue<_st> Q;	// 상태발전용 큐
	Q.push({ x, y });
	visited[x][y] = 1;

	std::vector<_st> E;	// 터질 뿌요 저장
	E.push_back({ x, y });

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > 12 - 1 || ny < 0 || ny > 6 - 1) continue;	// 영역밖이라면 스루
			if (board[nx][ny] == type && visited[nx][ny] == 0) {
				visited[nx][ny] = 1;
				Q.push({ nx, ny });
				E.push_back({ nx, ny });
			}
		}
	}
	if (E.size() >= 4) {
		for (_st pos : E) {
			board[pos.x][pos.y] = '.';
		}
		return true;
	}
	return false;
}



int map_scan()
{
	// 터질 수 있는 뿌요가 있는지 스캔 
	int del = 0;
	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {
			if (board[i][j] == '.') continue;
			if (BFS(board[i][j], i, j)) del++;	// 삭제됨 
		}
	}
	return del;
}


void get_down()
{
	// 모든 열에 대하여 수행 
	std::queue<char> D;
	for (int j = 0; j < 6; j++) {
		D = {};
		for (int i = 11; i >= 0; i--) {
			if (board[i][j] != '.') D.push(board[i][j]);
		}
		int d_size = D.size();
		for (int i = 11; i > 11 - d_size; i--) {
			board[i][j] = D.front();
			D.pop();
		}
		for (int i = 11 - d_size; i >= 0; i--) {
			board[i][j] = '.';
		}
	}
}



int game_start()
{
	// 연쇄 카운팅 
	int combo = 0;
	while (1) {
		int tmp = map_scan();
		if (tmp == 0) break;
		combo++;
		get_down();
	}
	return combo;
}



int main()
{
	input();
	int ans = game_start();
	printf("%d", ans);
	return 0;
}

음 .. 내가 앞으로 제일 싫어하는 게임 뿌요뿌요... 

 

 

// game_start( ) 함수 

문제에서 "터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고, 여러 그룹이 터지더라도 한 번의 연쇄가 추가된다"라고 했으므로, 한 게임에서 터트릴 수 있는 모든 뿌요를 다 터트리고 combo 수를 올려야 한다. 

while 문을 돌리면서 만약 tmp 변수가 0이 아니면 게임을 계속 진행하고(더 터트릴 그룹이 남아있는지 탐색), 만약 0이면 더이상 터트릴 뿌요 그룹이 없는 것이므로 break 한다. 

 

 

 

// map_scan ( ) 함수

전체 게임판을 스캔하면서 터트릴 수 있는 뿌요 그룹이 있는지 탐색한다. 만약 BFS함수가 true를 리턴하면, 한개의 뿌요 그룹을 터트린 것이므로 del 변수를 증가시킨다. 해당 변수는 game_start( ) 함수에서 맵을 한번 더 스캐닝 해야하는지 말아야 하는지 판단할 때 쓰인다. 

 

 

// BFS( ) 함수

이 함수를 호출할 때 마다 새로운 뿌요 그룹을 탐색할 것이기 때문에 방문 배열을 초기화 해준다. 

이때 선언한 큐 Q는 상태발전용이고, 벡터 E는 터질 뿌요를 저장하기 위함이다. 넘겨받은 파라미터 (x, y)에 위치한 종류가 type인 뿌요에서부터 상태 발전을 시작한다. 만약 상하좌우 인접한 곳에 같은 종류의, 아직 방문하지 않은 칸에 뿌요가 존재한다면 해당 좌표를 Q와 E에 각각 삽입한다. 

 

만약 벡터 E의 크기가 4 이상이라면, 즉 "같은 색의 뿌요들이 4개 이상 모이게 된 상황" 이므로 해당 뿌요 그룹에 속한 모든 뿌요들을 터트려준다. 즉 빈칸으로 만든다. 

만약 뿌요 그룹을 터트리는 이러한 과정을 진행했다면 true를 리턴하고, 터트리지 못했다면 false를 리턴한다. 

 

 

// get_down( ) 함수

한 번의 게임이 완료되고 뿌요를 내려주어야 한다. 

이를 위해 각 열을 탐색하면서 뿌요가 있으면 큐 D에 담아준다. 만약 뿌요가 없는 칸이면 아무 일도 일어나지 않고, 뿌요가 있어서 큐 D의 사이즈가 0보다 크면, 가장 마지막 행(11 행, 인덱스 0부터 시작했으므로) 부터 11 - D.size() 행 이전까지 각 칸에 뿌요를 삽입한다(위쪽에 있는 뿌요를 아래로 내림). 이때 D.size() 를 반드시 변수에 담아서 사용하는 것을 권고한다. D에있는 원소를 pop하면서 루프를 진행하는 과정에서 큐의 사이즈가 달라지기 때문이다. 

한편 11 - D.size() 행 부터 0번째 행 까지는 빈칸으로 바꿔준다(위에 있던 뿌요를 아래로 내렸으므로).