BaekJoon 11559번: Puyo Puyo(C++)

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

11559번: Puyo Puyo

풀이법

1) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다.

2) BFS알고리즘을 기준으로, 현재 색과 같은 색인 것들을 vector<pair<int,int>>에 index를 담아주었다가, 갯수가 4개 이상인 경우 이 값들을 빈 공간으로 바꾸어 주었다.

3) 한번이라도 4번 이상 뿌요가 터진 경우에는 totalCount라는 결과값을 증가 시켰고, 빈 공간을 채워주었다. 반면 한 번이라도 뿌요가 터지지 않은 반복이 일어난 경우 break해 주어서 시간 초과를 피하였다.

4) 밑 부분에 있는 공백을 없애기 위해서, 반복문을 활용하여 값을 채워주었다. (개인적으로 이 반복문을 작성하는 것이 이 문제의 핵심이라고 생각한다. 열을 기준으로 행의 값을 반복해서 아래로 내려 주는 것이 핵심이다.)

....G.
......
......
......
......
......
......
......
.Y....
.YG...
RRYG..
RRYGG.

위와 같이 엄청난 수의 공백이 발생했을 때를 대비하는 것이 핵심이다. 아래 첨부된 소스 코드를 읽어본 다면 위의 문제를 해결하는 방법을 알 수 있을 것이다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;

char arr[12][6];
char arr2[12][6];
bool visited[12][6];

int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
int totalCount = 0;
bool isDone()
{
	bool check = false;
	for (int i = 0; i < 12; i++)
	{
		for (int j = 0; j < 6; j++)
			if (arr[i][j] != '.')
				return true;
	}
	return false;
}
void clearVisit()
{
	for (int i = 0; i < 12; i++)
	{
		for (int j = 0; j < 6; j++)
		{
			visited[i][j] = false;
		}
	}
}

bool bfs(int a, int b)
{
	queue<pair<int, int>> q;
	visited[a][b] = true;
	q.push({a,b});
	vector<pair<int, int>> vec;
	int count = 0;
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second;
		q.pop();
		count++;
		vec.push_back({ nowX,nowY });

		for (int i = 0; i < 4; i++)
		{
			int nextX = nowX + vx[i];
			int nextY = nowY + vy[i];

			if (nextX < 0 || nextY < 0 || nextX >= 12 || nextY >= 6)
				continue;
			if (arr[nextX][nextY] == arr[nowX][nowY] && !visited[nextX][nextY])
			{
				visited[nextX][nextY] = true;
				q.push({ nextX,nextY });
			}
		}
	}
	if (count >= 4)
	{
		for (int i = 0; i < vec.size(); i++)
		{
			int nowX = vec[i].first;
			int nowY = vec[i].second;
			arr[nowX][nowY] = '.';
		}
		return true;
	}
	return false;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	for (int i = 0; i < 12; i++)
	{
		for (int j = 0; j < 6; j++)
			cin>>arr[i][j];
	}
	bool change;
	while (1)
	{
		clearVisit();
		change = false;
		for (int i = 0; i < 12; i++)
		{
			for (int j = 0; j < 6; j++)
			{ 
				if (arr[i][j] != '.'&&!visited[i][j])
				{
					bool check=bfs(i, j);
					if (check == true)
						change = true;
				}
				else
				{
					visited[i][j] == true;
				}
			}
		}
		if (change == false)
			break;
		else
		{
			totalCount++;
			for (int k = 0; k < 6; k++)
			{
				for (int i = 0; i < 12; i++)
				{
					for (int j = 10; j >= 0; j--)
					{
						if (arr[j + 1][k] == '.' && arr[j][k] != '.')
						{
							arr[j + 1][k] = arr[j][k];
							arr[j][k] = '.';
						}
					}
				}
			}
		}
	}
	cout << totalCount;
}