백준 - Puyo Puyo (11559)

1. 문제

문제 링크

설명

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

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

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

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

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

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

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

2. 풀이

BFS를 활용한 문제인 건 다들 아실겁니다.
이 문제에서 조금 까다로운 부분은

• 터질 푸요의 검사
• 푸요를 터뜨린 후, 아래로 떨어지게 하기

이 두 부분일 겁니다.
저는 모두 큐로 해결했습니다.

1. 필요한 큐의 선언

queue<pair<int, int>> explore, cand, explode;
queue<char> q;

• explore : 터질 푸요를 검사
  • 상하좌우로 인접한 푸요를 탐색하며 cand에도 좌표 넣기
• cand: 터질 후보가 되는 푸요를 저장
  • 크기가 4 이상일 때 explode에 저장
• explode: 터질 푸요를 저장
  • 저장된 푸요를 한 번에 다 터트림

2. 터질 푸요 검사

explore.push({ i, j });
visited[i][j] = 1;

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

	// 터질 후보큐에 넣어준다.
	cand.push(explore.front());
	explore.pop();

	for (int dir = 0; dir < 4; dir++) {
		int ny = y + my[dir];
		int nx = x + mx[dir];

		if (ny < 0 || ny >= ROW || nx < 0 || nx >= COL) continue;

		if (board[ny][nx] != board[i][j]) continue;

		if (visited[ny][nx]) continue;

		explore.push({ ny, nx });
		visited[ny][nx] = 1;
	}
}

3. 터져야되는 푸요면 explode에 넣기

// 4개 이상 모여있으면 터져야한다.
bool isExplode = cand.size() >= 4;

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

	if (isExplode) {
		explode.push(cand.front());
	}

	visited[y][x] = 0;
	cand.pop();
}

4. 푸요 터트리기

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

	explode.pop();
	board[y][x] = '.';
	explodeCol[x] = 1;
}

explodeCol은 폭발한 푸요가 있는 컬럼을 검사합니다.
해당 컬럼에 있는 푸요만 아래로 내려줍니다.

5. 푸요 내리기

for (int c = 0; c < COL; c++) {
	// 푸요가 터진 컬럼이 아니면 넘어가기
	if (!explodeCol[c]) continue;

	// 밑에서부터 '.'이 아닌 애들을 큐에 넣기
	for (int r = ROW - 1; r >= 0; r--) {
		if (board[r][c] == '.') continue;

		q.push(board[r][c]);
		board[r][c] = '.';
	}

	int r = ROW - 1;

	// 큐에서 하나씩 빼면서 밑에서부터 채워주기
	while (!q.empty()) {
		board[r--][c] = q.front();
		q.pop();
	}

	explodeCol[c] = 0;
}

이런 식으로 반복하면 쉽게 문제를 해결할 수 있습니다.

3. 전체 코드

#define ROW 12
#define COL 6
#include <bits/stdc++.h>

using namespace std;

char board[ROW][COL];
int visited[ROW][COL];
int explodeCol[COL];
int my[4] = { -1, 0, 1, 0 };
int mx[4] = { 0, 1, 0, -1 };
int n = -1;
queue<pair<int, int>> explore, cand, explode;
queue<char> q;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < ROW; i++) {
		for (int j = 0; j < COL; j++) {
			cin >> board[i][j];

			if (board[i][j] != '.' && n != -1) {
				n = i;
			}
		}
	}

	int ans = 0;

	while (1) {
		for (int i = n; i < ROW; i++) {
			for (int j = 0; j < COL; j++) {
				if (board[i][j] == '.') continue;

				explore.push({ i, j });
				visited[i][j] = 1;

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

					// 터질 후보큐에 넣어준다.
					cand.push(explore.front());
					explore.pop();

					for (int dir = 0; dir < 4; dir++) {
						int ny = y + my[dir];
						int nx = x + mx[dir];

						if (ny < 0 || ny >= ROW || nx < 0 || nx >= COL) continue;

						if (board[ny][nx] != board[i][j]) continue;

						if (visited[ny][nx]) continue;

						explore.push({ ny, nx });
						visited[ny][nx] = 1;
					}
				}

				// 4개 이상 모여있으면 터져야한다.
				bool isExplode = cand.size() >= 4;

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

					if (isExplode) {
						explode.push(cand.front());
					}

					visited[y][x] = 0;
					cand.pop();
				}
			}
		}

		if (explode.empty()) break;

		ans++;

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

			explode.pop();
			board[y][x] = '.';
			explodeCol[x] = 1;
		}

		for (int c = 0; c < COL; c++) {
			// 푸요가 터진 컬럼이 아니면 넘어가기
			if (!explodeCol[c]) continue;

			// 밑에서부터 '.'이 아닌 애들을 큐에 넣기
			for (int r = ROW - 1; r >= 0; r--) {
				if (board[r][c] == '.') continue;

				q.push(board[r][c]);
				board[r][c] = '.';
			}

			int r = ROW - 1;

			// 큐에서 하나씩 빼면서 밑에서부터 채워주기
			while (!q.empty()) {
				board[r--][c] = q.front();
				q.pop();
			}

			explodeCol[c] = 0;
		}
	}

	cout << ans;

	return 0;
}