백준 11559 Puyo Puyo

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

11559번: Puyo Puyo

문제

뿌요뿌요의 룰은 다음과 같다.

필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.

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

뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.

아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.

터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.

남규는 최근 뿌요뿌요 게임에 푹 빠졌다. 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다. 하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다. 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!

입력

총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다.

이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다.

R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.

입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태이다. 즉, 뿌요 아래에 빈 칸이 있는 경우는 없다.

출력

현재 주어진 상황에서 몇연쇄가 되는지 출력한다. 하나도 터지지 않는다면 0을 출력한다.

예제 입력 1 

......

......

......

......

......

......

......

......

.Y....

.YG...

RRYG..

RRYGG.

예제 출력 1 

3

---

[풀이 과정]

1. arr배열에 1글자씩 입력을 받는다.

2. 사라질 뿌요가 없을 때까지 반복문을 실행한다.

- check함수가 true인 경우 계속 실행하고 false일 경우 반복문을 멈춘다.

 

3. check()

- 모든 위치를 탐색하면서 점(.)이 아니고 방문하지 않은 곳이면 bfs를 실행한다.

- bfs의 결과가 true이면 사라진 뿌요가 있는 것이므로 true를 반환한다.

- bfs의 결과가 false이면 사라진 뿌요가 없는 것이므로 false를 반환한다.

 

4. bfs(int a, int b)

- 현재 위치를 방문표시한다.

- 다음 위치 탐색을 위해 q에 push한다.

- q2에도 같은 위치 값을 push하는데 이는 4개 이상 모여있는지 확인하고 터트리기 위해 사용할 큐이다.

- q에 있는 값들을 가지고 상하좌우로 탐색을 시작한다.

- 다음 위치가 범위 밖이면 패스한다.

- 다음 위치가 방문 전이고 현재 색과 같은 색이면 방문 표시 후 q, q2에 모두 push한다.

- q에 있는 모든 값을 탐색 한 후에 q2에는 같은 색들의 위치가 저장되어있다.

- q2의 크기가 4 이상인지 확인 후 4 이상이면 하나씩 값을 가져다가 빈 곳으로 바꿔준 후 true를 반환한다.

- q2의 크기가 4 미만이면 터질 뿌요가 없으므로 false를 리턴한다.

 

5. gravity()

- 값 들이 아래로 내려와야하므로 마지막 행부터 첫번째 행 순서로 탐색한다.

- 만약 현재 위치가 빈 칸이라면 현재 위치의 윗 행부터 0번재 행까지 탐색하면서 값이 있는 칸을 찾아 그 값을 현재 위치에 채우고 그 칸은 빈 칸으로 바꾼 후 탐색을 멈춘다.

- 모든 위치에 대해 위 과정을 반복한다.

 

6. 한 사이클이 돌면 time을 1 증가시킨다.

 

7. 더이상 터질 뿌요가 없으면 반복문을 멈추고 time을 출력한다.

---

[소스 코드]

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

char arr[15][10];
bool visited[15][10];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };

bool bfs(int a, int b) {
	visited[a][b] = true;
	queue <pair<int, int>> q;
	queue <pair<int, int>> q2;
	q.push(make_pair(a, b));
	q2.push(make_pair(a, b));

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

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

			if (nx < 0 || nx >= 12 || ny < 0 || ny >= 6) continue;

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

	}

	if (q2.size() >= 4) {
		while (!q2.empty()) {
			int x = q2.front().first;
			int y = q2.front().second;
			q2.pop();

			arr[x][y] = '.';
		}

		return true;
	}
	return false;
}
bool check() {
	bool result = false;
	memset(visited, 0, sizeof(visited));

	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {
			if (arr[i][j] == '.') continue;

			if (!visited[i][j]) {
				bool res = bfs(i, j);
				if (res) result = true;
			}
		}
	}
	return result;
}

void gravity() {
	for (int i = 11; i >= 1; i--) {
		for (int j = 0; j < 6; j++) {
			if (arr[i][j] == '.') {

				for (int k = i - 1; k >= 0; k--) {
					if (arr[k][j] == '.') continue;
					arr[i][j] = arr[k][j];
					arr[k][j] = '.';
					break;
				}
			}
		}
	}
}

int main() {
	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {
			scanf(" %1c", &arr[i][j]);
		}
	}

	int time = 0;
	while (1) {
		if (!check()) break;
		gravity();
		time++;
	}
	printf("%d\n", time);
	return 0;
}