[BOJ]백준 11559번: Puyo Puyo

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

11559번: Puyo Puyo

삼성 역테를 준비중이라면 다들 풀어봤을 대표적인 구현문제

뿌요뿌요의 특징은

1. 같은 색 뿌요가 4개 이상 연결(상하좌우)되어있을 경우 터진다

    for(모든 좌표를 탐색)

        연결요소 수 = bfs(현재좌표)

        if(연결요소 수>=4)

            현재 좌표와 연결된 요소들 '.'로 변경한다

2. 한번에 여러 그룹이 터지는게 가능할 경우 동시에 터진다

3. 공중에 떠있을 경우 중력의 영향을 받아 아래로 떨어진다

    for(행 탐색)

        for(열 탐색)

            뿌요가 있을경우 큐에 삽입

        for(열 탐색)

            아래에서부터 큐에 있던 뿌요를 쌓는다

이 문제를 품으로써 한 단계 성장할 수 있었읍니다...^__^

 

#include <cstdio>
#include <string.h>
#include <queue>
using namespace std;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, cnt, ans, m;
char map[13][7];
bool visit[13][7];
struct point { int x, y; };
queue<point> q;
queue<char> tmp;
bool safe(int x, int y) {
	return y >= 0 && y < 12 && x >= 0 && x < 6;
}
int bfs(point p, char o) {
	visit[p.y][p.x] = true;
	q.push(p); cnt = 1;
	while (!q.empty()) {
		point cp = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cp.x + dx[i], ny = cp.y + dy[i];
			if (map[ny][nx] == o && safe(nx, ny) && !visit[ny][nx]) {
				visit[ny][nx] = true;
				q.push({ nx,ny });
				cnt++;
			}
		}
	}
	return cnt;
}
int main() {
	for (int i = 0; i < 12; i++) {
		scanf(" %c", &map[i][0]);
		for (int j = 1; j < 6; j++)
			scanf("%c", &map[i][j]);
	}
	do {
		m = 0;
		for (int i = 0, cnt = 0; i < 12; i++)
			for (int j = 0; j < 6; j++) {
				memset(visit, false, sizeof(visit));
				if (map[i][j] != '.' && !visit[i][j]) {
					cnt = bfs({ j,i }, map[i][j]);
					m = cnt > m ? cnt : m;
				}
				if (cnt >= 4) {
					for (int a = 0; a < 12; a++)
						for (int b = 0; b < 6; b++)
							if (visit[a][b])map[a][b] = '.';
				}
			}
		for (int a = 0; a < 6; a++) {
			for (int b = 11; b >= 0; b--)
				if (map[b][a] != '.')
					tmp.push(map[b][a]);
			for (int b = 11; b >= 0; b--)
				if (!tmp.empty()) {
					map[b][a] = tmp.front(); tmp.pop();
				}
				else
					map[b][a] = '.';
		}
		if (m >= 4)ans++;
	} while (m >= 4);
	printf("%d", ans);
	return 0;
}