백준 11559 : Puyo Puyo c++

www.acmicpc.net/problem/11559

후기 겸 풀이

1. 생각보다 쉬운 문제다 구현만 잘하면 된다

 

2. 한 루프당

부셔질수 있는 블록들 체크 -> (부술수 있는게 없으면 게임 종료) -> 부셔질 블록들 제거 -> 부셔지고 남은 자리 채우기

 

반복

 

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

char map[12][6];// 뿌요뿌요
int check[12][6] = { 0, };
int visited[12][6] = { 0, };
vector<pair<int, int> > team;

int d_r[4] = { 1,-1,0,0 };
int d_c[4] = { 0,0,1,-1 };


bool break_possible()
{
	for (int i = 0; i < 12; i++)
		for (int j = 0; j < 6; j++)
		{
			if (check[i][j] != 0)//하나라도 뿌실게 있으면!
				return true;
		}

	return false;
}

void bfs(int r,int c)
{
	char a = map[r][c];
	queue<pair<int, int> > q;
	q.push(make_pair(r, c));
	visited[r][c] = 1;
	while (!q.empty())
	{
		int r1 = q.front().first;
		int c1 = q.front().second;
		q.pop();
		team.push_back(make_pair(r1,c1));//큐에 들갔다는거는 같은 색깔이라는 뜻

		for (int i = 0; i < 4; i++)
		{
			int new_r = r1 + d_r[i];
			int new_c = c1 + d_c[i];

			if (new_r < 0 || new_c < 0 || new_r >= 12 || new_c >= 6)
				continue;
			if (visited[new_r][new_c] == 1)
				continue;
			if (map[new_r][new_c] != a)
				continue;

			visited[new_r][new_c] = 1;
			q.push(make_pair(new_r, new_c));

		}

	}
}

void destroy()
{
	for (int i = 0; i < 12; i++)
		for (int j = 0; j < 6; j++)
		{
			if (check[i][j] != 0)
				map[i][j] = '.';
		}


}

void go_down()
{
	vector<char> a;
	for (int j = 0; j < 6; j++)//열
	{
		a.clear();
		for (int i = 11; i >= 0; i--)//헹
		{
			if (map[i][j] != '.')//빈칸 아니면!
			{
				a.push_back(map[i][j]);
			}
		}
		for (int i = 0; i < a.size(); i++)
		{
			map[11 - i][j] = a[i];
		}
		for (int i = 11 - a.size(); i >= 0; i--)
		{
			map[i][j] = '.';
		}

	}

}

int main()
{
	for(int i=0;i<12;i++)
		for (int j = 0;j < 6; j++)
		{
			cin >> map[i][j];
		}
	int result = 0;

	while (true)
	{

		memset(check, 0, sizeof(check));

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

				memset(visited, 0, sizeof(visited));

				if (check[i][j] == 1)
					continue;//이미 뿌시기로 정하거면 굳이 판단 X
					
				bfs(i,j);//bfs 로 연결된거 team 벡터에 집어넣기

				if (team.size() >= 4)
				{
					for (int f = 0; f < team.size(); f++)
					{
						check[team[f].first][team[f].second] = 1;
					}
				}

				team.clear();
			}

		//뿌실게 없다
		if (break_possible() == false)
		{
			break;
		}

		
		destroy();//지정한 벽돌들 뿌수기
		go_down();

		
		result++;
	}

	cout << result << endl;
	return 0;
}