백준 11559 - Puyo Puyo(C++)

문제 링크입니다. https://www.acmicpc.net/problem/11559

11559번: Puyo Puyo

BFS와 구현이 합쳐진 문제였습니다.

문제 조건

출력 예시

같은 색깔의 뿌요가 4개 이상인지를 찾은 뒤, 해당 뿌요들을 없앱니다. 그 뒤, 남아있는 뿌요를 아래로 내린 뒤, 다시 뿌요 그룹을 찾는 문제였습니다. 

 

1. 같은 색의 뿌요 찾기

void puyo_boom(int a, int b, char c) {
	queue<qu> q;
	q.push({ a,b });
	check[a][b] = 1;
	int cnt = 1;
	while (!q.empty()) {
		int x1 = q.front().x;
		int y1 = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x1 + arr[i];
			int yy = y1 + arr2[i];
			if (xx >= 1 && yy >= 1 && xx <= 12 && yy <= 6) {
				if (check[xx][yy] == 0 && puyo[xx][yy] == c) {
					cnt++;
					check[xx][yy] = 1;
					q.push({ xx,yy });
					boom.push({ xx,yy });
				}
			}
		}
	}
	//cout << cnt << " ";
	if (cnt < 4) {
		while (!boom.empty()) boom.pop();
	}
	else if (cnt >= 4) {
		get_ = true;
		get_rid();
	}
}

빈칸이 아니면서, 이전에 방문하지 않은 좌표일 경우, puyo_boom 함수에 넣어줬습니다.

해당 좌표에서 4방향 탐색을 통해 같은 색깔을 찾은 뒤, 해당 좌표를 저장했습니다.

 

4개 이상의 뿌요가 그룹에 있을 경우, 해당 좌표를 빈칸으로 만들어줬습니다.

get_ 변수의 경우, 없앨 수 있는 뿌요가 있는지의 여부입니다. 

 

 

2. 뿌요 내리기

void down_puyo() {
	for (int i = 11; i >= 1; i--) {
		for (int j = 6; j >= 1; j--) {
			if (puyo[i][j] != '.') {
				int x = i;
				int y = j;
				while (1) {
					if (x + 1 <= 12) {
						if (puyo[x + 1][y] == '.') {
							puyo[x + 1][y] = puyo[x][y];
							puyo[x][y] = '.';
							x = x + 1;
						}
						else break;
					}
					else break;

				}
			}
		}
	}
}

뿌요를 내리는 코드입니다. 

아랫줄부터 시작하면 쉽게 내릴 수 있습니다.

 

while문을 통해, 자신의 아랫 칸이 빈칸일 경우 계속 내려줬습니다.

 

 

문제 접근 방법

1. 뿌요 그룹이 있는지를 확인한다.

2. 뿌요 그룹 중, 4개 이상의 뿌요로 이루어진 그룹이 있다면 없애준다.

3. 뿌요를 내려준다.

4. 1~3 과정을 4개 이상으로 이루어진 그룹을 찾을 수 없을때까지 반복한다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>

int chain;
bool get_;
using namespace std;
char puyo[20][7];
int check[13][7];
typedef struct qu {
	int x;
	int y;
}qu;
int arr[4] = { 1,-1,0,0 };
int arr2[4] = { 0,0,1,-1 };
queue<qu> boom;

void down_puyo();

void get_rid() {
	while (!boom.empty()) {
		int x1 = boom.front().x;
		int y1 = boom.front().y;
		boom.pop();
		puyo[x1][y1] = '.';
	}
}
void reset_check() {
	for (int i = 1; i <= 12; i++) {
		for (int j = 1; j <= 6; j++) {
			check[i][j] = 0;
		}
	}
}

void puyo_boom(int a, int b, char c) {
	queue<qu> q;
	q.push({ a,b });
	check[a][b] = 1;
	int cnt = 1;
	while (!q.empty()) {
		int x1 = q.front().x;
		int y1 = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x1 + arr[i];
			int yy = y1 + arr2[i];
			if (xx >= 1 && yy >= 1 && xx <= 12 && yy <= 6) {
				if (check[xx][yy] == 0 && puyo[xx][yy] == c) {
					cnt++;
					check[xx][yy] = 1;
					q.push({ xx,yy });
					boom.push({ xx,yy });
				}
			}
		}
	}
	//cout << cnt << " ";
	if (cnt < 4) {
		while (!boom.empty()) boom.pop();
	}
	else if (cnt >= 4) {
		get_ = true;
		get_rid();
	}
}

void down_puyo() {
	for (int i = 11; i >= 1; i--) {
		for (int j = 6; j >= 1; j--) {
			if (puyo[i][j] != '.') {
				int x = i;
				int y = j;
				while (1) {
					if (x + 1 <= 12) {
						if (puyo[x + 1][y] == '.') {
							puyo[x + 1][y] = puyo[x][y];
							puyo[x][y] = '.';
							x = x + 1;
						}
						else break;
					}
					else break;

				}
			}
		}
	}

}

void solve() {
	while (1) {
		for (int i = 1; i <= 12; i++) {
			for (int j = 1; j <= 6; j++) {
				if (puyo[i][j] != '.' && check[i][j] == 0) {
					boom.push({ i,j });
					puyo_boom(i, j, puyo[i][j]);
				}
			}
		}
		if (get_ == false) break;
		reset_check();
		down_puyo();
		chain++;
		//cout << chain << "\n";
		get_ = false;
	}
	cout << chain;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	for (int i = 1; i <= 12; i++) {
		for (int j = 1; j <= 6; j++) {
			cin >> puyo[i][j];
		}
	}
	solve();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요!