[백준/BOJ] 백준 11559번 : Puyo Puyo

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

11559번: Puyo Puyo

연결되어 있는 같은 색 뿌요들의 정보를 저장하는 함수와 뿌요들을 아래로 떨어트리는 함수를 만들어 Solve()를 통해 연쇄의 개수를 구했다.

 

코드

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

vector<string> board;
int visited[12][6];
int dx_dy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

//연결되어 있는 같은 색 뿌요들의 정보를 저장
void areaCheck(pair<int, int> here, char kind, vector<pair<int, int>>& this_area)
{
	visited[here.first][here.second] = 1;
	this_area.push_back(here);

	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);

		if (there.first >= 0 && there.first < 12 && there.second >= 0 && there.second < 6 && board[there.first][there.second] == kind && visited[there.first][there.second] == 0)
		{
			areaCheck(there, kind, this_area);
		}
	}
}

//뿌요들 아래로 떨어뜨리기
void downMove()
{

	for (int j = 0; j < 6; j++)
		for (int i = 10; i >= 0; i--)
		{
			if (board[i][j] != '.')
			{
				int down_x = i;

				while (down_x + 1 <= 11 && board[down_x + 1][j] == '.')
				{
					down_x++;
				}

				if (board[down_x][j] != board[i][j])
				{
					board[down_x][j] = board[i][j];
					board[i][j] = '.';
				}
			}
		}
}

int Solve()
{
	int ret = 0;
	bool change = true;

	while (change)
	{
		change = false;
		memset(visited, 0, sizeof(visited));

		for (int i = 0; i < 12; i++)
			for (int j = 0; j < 6; j++)
			{
				if (board[i][j] != '.' && visited[i][j] == 0)
				{
					vector<pair<int, int>> this_area;
					areaCheck(make_pair(i, j), board[i][j], this_area);

					//연결된 같은 색의 뿌요가 4개 이상일때
					if (this_area.size() >= 4)
					{
						for (int k = 0; k < this_area.size(); k++)
							board[this_area[k].first][this_area[k].second] = '.';

						change = true;
					}
				}
			}
		//바뀐게 있다면 연쇄 증가
		if (change)
			ret++;

		//뿌요들 아래로 떨어지게 하기
		downMove();
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	string temp;

	for (int i = 0; i < 12; i++)
	{
		cin >> temp;
		board.push_back(temp);
	}

	cout << Solve();

	return 0;
}