BOJ : 11559 Puyo Puyo

 

---

[BOJ 11559(G5) 리뷰]

 

뿌요뿌요 문제다. 같은색의 뿌요가 4개인접해있으면 그 뿌요들은 터지며 없어진다. (애니팡과 비슷)

뿌요가 터지면 위에있는 뿌요들은 아래로 모두 내려오게 되며 아래로 내려왔을때 4개이상 인접해있는 뿌요가 있다면 또 터지게 된다.

이 때 연속적으로 몇번의 차례동안 뿌요가 터지는지 계산하는 문제이다.

애니팡을 해봤으면 하나를 터트렸을때 터진자리에 새로운 캐릭터가 채워지면서 연쇄적으로 터지는걸 경험한적이 있을것이다. 그걸 생각하며 구현하면 된다.

 

같은색의 뿌요를 찾는 BFS와 뿌요가 터진 후 뿌요들을 아래로 내려주는 함수를 구현하면 된다.

 

 

---

#include <iostream>
#include <queue>
#include <math.h>
#include <set>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <string.h>
using namespace std;

#define R 12
#define C 6

#define X first
#define Y second

char board[13][7];


int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int ans = 0;

void move()
{
	for (int i = 0; i <C ; i++)
	{
		for (int j = R-1; j >= 0; j--)
		{
			if (board[j][i] == '.') continue;
			char color = board[j][i];
			for (int k = j + 1; k < R; k++)
			{
				if (board[k][i] != '.')
				{
					board[j][i] = '.';
					board[k - 1][i] = color;
					break;
				}
				else if (k == R - 1)
				{
					board[k][i] = color;
					board[j][i] = '.';
					break;
				}
			}

		}
	}

}

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

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			cin >> board[i][j];
		}
	}
	
	while (1)
	{
		bool vis[13][7] = { 0, };
		bool isValid = false;
		for (int i = 0; i < R; i++)
		{
			for (int j = 0; j < C; j++)
			{
				if (board[i][j] == '.' || vis[i][j]) continue;
				queue <pair<int, int>> Q;
				stack <pair<int, int>> st;
				char color = board[i][j];
				Q.push({ i,j });
				st.push({ i,j });
				vis[i][j] = 1;
				int cnt = 1;
				while (!Q.empty())
				{
					auto cur = Q.front(); Q.pop();
					for (int dir = 0; dir < 4; dir++)
					{
						int nx = cur.X + dx[dir];
						int ny = cur.Y + dy[dir];
						if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
						if (vis[nx][ny] || board[nx][ny] != color) continue;
						vis[nx][ny] = 1;
						Q.push({ nx,ny });
						st.push({ nx,ny });
						cnt++;
					}
				}
	
				if (cnt >= 4) //펑펑
				{
					for (int i = 0; i < cnt; i++)
					{
						auto cur = st.top(); st.pop();
						board[cur.X][cur.Y] = '.';
					}
					isValid = true;
				}
				
			}
		}
		if (!isValid) break;
		ans += 1;
		move();
	}


	//cout << '\n';
	//for (int i = 0; i < R; i++)
	//{
	//	for (int j = 0; j < C; j++)
	//	{
	//		cout << board[i][j];
	//	}
	//	cout << '\n';
	//}

	cout << ans;
	
}