BOJ11559 Puyo Puyo

[BOJ11559] Puyo Puyo

BOJ PuyoPuyo 문제 링크

문제 설명

1. 필드에 여러가지 색상의 뿌요를 놓는다.
2. 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 같은 색 뿌요들이 한번에 없어진다.
3. 뿌요가 없어지고 나서 위에 다른 뿌요들이 있다면, 중력의 영향으로 아래로 떨어진다.
4. 한번에 터질 수 있는 뿌요들은 동시에 터진다.
5. 그렇게 동시에 터지는 연쇄상황이 몇 번 일어나는지 구하는 문제.

코드 리뷰

• 뿌요 구조체를 만들고, 큐를 두개 만들었다.(같은색 뿌요를 탐색하기 위한 큐(q), 터지는 뿌요가 4개이상인지 확인하는 큐(checkq)
• 뿌요 탐색은 BFS를 통해서 하였고, BFS를 하면서 checkq에 탐색한 뿌요들을 집어 넣었다.
• 탐색이 끝나면 checkq의 사이즈를 확인하고, 4이상일 경우 그 필드를 ‘.’으로 바꾼다.
• 모든 필드에 대한 확인이 끝나고 나면 boardsort 함수를 통해 뿌요들을 재정렬 시킨다.(벽돌깨기 문제랑 똑같음)
• 연쇄작용에 대한 CNT를 출력

/* BOJ 11559 Puyo Puyo*/

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

char board[15][8];
int check[15][8];

typedef struct { //뿌요 구조체
	int x;
	int y;
	char color;
}Node;

queue <Node> checkq; //터지는 뿌요가 몇개인지 체크하는 큐
queue <Node> q; //같은 색 뿌요를 탐색하기 위한 큐
int dc[4] = { 0,0,-1,1 };
int dr[4] = { -1,1,0,0 };

void bfs() { //뿌요를 탐색한다
	while (q.empty() == 0) {
		int xnow = q.front().x;
		int ynow = q.front().y;
		char nowcol = q.front().color;
		checkq.push({ xnow,ynow,nowcol }); //뿌요를 checkq에 집어넣어 나중에 몇개의 뿌요를 탐색했는지 개수파악
		check[xnow][ynow] = 1;
		q.pop();
		for (int k = 0; k < 4; k++) {
			int xnext = xnow + dc[k];
			int ynext = ynow + dr[k];
			if (board[xnext][ynext] == nowcol && xnext >= 0 && xnext < 12 && ynext >= 0 && ynext < 6 && check[xnext][ynext] == 0) {
				Node point = { xnext,ynext,board[xnext][ynext]};
				q.push(point);
				check[xnext][ynext] = 1;
			}
		}
	}
}

void boardsort() { //한번의 연쇄작용이 끝난 후 뿌요들 재정렬
	for (int i = 0; i < 6; i++) {
		for (int j = 11; j > 0; j--) {
			if (board[j][i] == '.') {
				for (int k = j - 1; k >= 0; k--) {
					if (board[k][i] != '.') {
						board[j][i] = board[k][i];
						board[k][i] = '.';
						break;
					}
				}
			}
		}
	}
}
int main() {
	for (int i = 0; i < 12; i++) {
		scanf("%s", &board[i]);
	}
	int cnt = 0;
	int checkbomb = 1;
	while (checkbomb != 0) { //checkbomb는 4개이상의 뿌요가 터질때 올려주는 변수
		checkbomb = 0;
		for (int i = 0; i < 12; i++) {
			for (int j = 0; j < 6; j++) {
				if (board[i][j] == '.') continue;
				else {
					if (check[i][j] == 0) {
						Node point = { i,j,board[i][j] }; //뿌요하나를 탐색하기 위해 정보입력
						q.push(point); //뿌요 탐색을 위해 q에 푸쉬
						bfs();
						if (checkq.size() < 4) { //checkq의 사이즈가 4보다 작을땐 어떠한 변화도 없다
							while (checkq.empty() == 0) checkq.pop(); //pop만 하면됨
						}
						else if (checkq.size() >= 4) { //4보다 클땐 checkbomb 올려줘서 4개이상 뿌요가 터졋다는 걸 표시
							checkbomb++;
							while (checkq.empty() == 0) {// checkq를 비우면서 보드판도 . 으로 바꿔준다
								int nowx = checkq.front().x;
								int nowy = checkq.front().y;
								board[nowx][nowy] = '.';
								checkq.pop();
							}
						}
					}
				}
			}
		}
		if (checkbomb > 0) cnt++; // 4개이상의 뿌요가 터진 경우가 존재할때 연쇄폭발 한번 증가
		boardsort();
		memset(check, 0, sizeof(check));
	}
	printf("%d\n", cnt);
	return 0;
}

문제 리뷰

• 벽돌깨기를 풀고나서 그런지 문제 자체는 어렵지 않았다.
• 보드판이 작아서 그냥 완전탐색을 했는데, 보드판이 클 경우에 대해 생각도 해봐야겠다.
• 다음에 풀때는 조금 더 코드를 다듬어 봐야지.