취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11559번 문제인 Puyo Puyo이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11559

현재 뿌요뿌요 게임판이 주어졌을 때(단, 뿌요들은 전부 아래로 떨어진 뒤의 상태이다) 총 몇 연쇄를 하게 될지 시뮬레이션을 통해 구하는 문제이다.

이 문제를 해결하기 위해서 글쓴이는 다음과 같은 함수들을 구상하였다.

1) chain 함수

이 함수는 현재의 게임판에서 터질 수 있는 뿌요를 모두 터뜨린다.

다른 말로 하면 chain 함수는 터질 수 있는 뿌요를 모두 "."으로 바꾸는 함수이다.

만약 터뜨린 뿌요가 있다면 1을, 없다면 0을 리턴한다.

이 리턴값은 터뜨린 뿌요가 있다면 연쇄 수를 1 증가시키고 그렇지 않다면 시뮬레이션을 중단시킬 정보로 사용할 수 있다.

보드판에서 터질 수 있는 뿌요를 탐색하는 것은 dfs 또는 bfs등의 탐색으로 각 ('.'이 아닌 게임판 위에서) connected component의 크기를 구하는 것으로 간단히 할 수 있다.

2) drop 함수

이 함수는 막 뿌요가 터진 게임판에서 뿌요를 아래로 떨어뜨리는 함수이다.

글쓴이는 이 함수를 다음과 같이 구현하였다.

2-1) 현재 세로줄에서 바닥으로부터 첫 빈 공간이 나오는 가로줄 A를 찾는다. 없다면 다음 세로줄로 넘어간다.

2-2) 첫 빈 공간으로부터 처음으로 뿌요가 나오는 가로줄 B를 찾는다. 없다면 다음 세로줄로 넘어간다.

2-3) B와 그 위쪽의 뿌요와 빈칸을 그대로 A와 그 위쪽으로 옮긴다.

2-4) 2-1로 돌아간다. (다음 세로줄로 넘어가지 않는다)

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

string board[12];
int visited[12][6];
vector<pair<int, int>> puyostk;
vector<pair<int, int>> dfsstk;

void drop() {
	for (int j = 0; j < 6; j++) {
		bool firstblank = 1;
		int i = 0;
		for (; i < 12; i++) {
			if (board[i][j] == '.') {
				firstblank = 0;
				break;
			}
		}
		
		if (firstblank) continue;

		int ii = i + 1;
		bool nextexist = 0;
		for (; ii < 12; ii++) {
			if (board[ii][j] != '.') {
				nextexist = 1;
				break;
			}
		}

		if (!nextexist) continue;
		
		for (; ii < 12; ii++) {
			board[i][j] = board[ii][j];
			board[ii][j] = '.';
			i++;
		}
		j--;
	}
}

int di[4] = { 1,-1,0,0 };
int dj[4] = { 0,0,1,-1 };

void dfs() {
	while (!dfsstk.empty()) {
		auto current = dfsstk.back();
		dfsstk.pop_back();

		int i = current.first;
		int j = current.second;
		puyostk.push_back(current);

		for (int k = 0; k < 4; k++) {
			int ii = i + di[k];
			int jj = j + dj[k];
			if (ii < 0 || ii >= 12 || jj < 0 || jj >= 6) continue;
			if (!visited[ii][jj] && board[ii][jj] == board[i][j]) {
				visited[ii][jj] = 1;
				dfsstk.push_back({ ii,jj });
			}
		}
	}
}

bool chain() {
	bool ret = 0;
	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {
			if (!visited[i][j] && board[i][j] != '.') {
				dfsstk.push_back({ i,j });
				visited[i][j] = 1;
				dfs();
				if (puyostk.size() >= 4) {
					ret = 1;
					for (auto node : puyostk) {
						board[node.first][node.second] = '.';
					}
				}
				puyostk.clear();
			}
		}
	}
	return ret;
}

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

	for (int i = 11; i >= 0; i--) cin >> board[i];

	int ans = 0;
	while (chain()) {
		ans++;
		memset(visited, 0, sizeof(visited));
		drop();
	}

	cout << ans << '\n';
}