백준 11559 c++

어렵긴 한데 도형을 다루다 보니 재밌게 풀었다. 알고리즘은 맞게 풀었지만 오류가 생긴 부분이 한 턴에서 몇개의 뿌요뿌요를 터뜨리던 count는 1만 증가한다. 터뜨린 뿌요뿌요의 수만큼이 아니라.

1. 순차 탐색을 하던 중 .이 아닌 뿌요뿌요를 발견
2. BFS를 통해 터뜨릴 수 있는 뿌요뿌요인지 아닌지 판단
3. 터뜨릴 수 있는 뿌요뿌요일 경우 전부 .으로 교체
4. 남은 순차탐색을 이어 가며 이번 턴에 터뜨릴 수 있는 모든 뿌요뿌요를 터뜨림
5. board에서 내릴수 있는 뿌요뿌요를 모두 내리는 작업과 visited를 초기화 하며 count를 1 증가
6. 위의 과정을 반복
7. 더 이상 board의 변화가 없다면 중단하고 결과 출력

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<vector<char>>board(12, vector<char> (6));
vector<vector<bool>>visited(12, vector<bool>(6, false));
int H = board.size(), W = board[0].size();

void input_puyopuyo()
{
	int i, j;

	for (i = 0; i < H; i++)
	{
		for (j = 0; j < W; j++)
		{
			cin >> board[i][j];
		}
	}

	/*for (i = 0; i < H; i++)
	{
		for (j = 0; j < W; j++)
		{
			cout << board[i][j];
		}
		cout << "\n";
	}*/

	return;
}

void reinit_visited()
{
	//cout << "reinit_visited() 수행\n";
	int i, j;

	for (i = 0; i < H; i++)
	{
		for (j = 0; j < W; j++)
		{
			visited[i][j] = false;
		}
	}

	return;
}

void reinit_board()
{
	//cout << "reinit_board()\n";
	int i, j, k;

	//확인용
	/*for (i = 0; i < H; i++)
	{
		for (j = 0; j < W; j++)
		{
			cout << board[i][j];
		}
		cout << "\n";
	}
	cout << "\n";*/

	for (i = 0; i < W; i++)//세로선 하나씩 확인
	{
		for (j = H - 1; j >= 1; j--)//높이 기준
		{
			if (board[j][i] == '.')//'.'을 발견
			{
				for (k = j - 1; k >= 0; k--)
				{
					if (board[k][i] != '.')
					{
						board[j][i] = board[k][i];
						board[k][i] = '.';
						break;
					}
				}
			}
		}
	}

	//확인용
	/*for (i = 0; i < H; i++)
	{
		for (j = 0; j < W; j++)
		{
			cout << board[i][j];
		}
		cout << "\n";
	}
	cout << "\n";*/

	return;
}

//현재 뿌요뿌요 색에 대해서 BFS로 연결된 모든 뿌요뿌요 확인
void BFS(int start_x, int start_y, char color, /*int* count,*/ bool* continue_puyopuyo)
{
	//cout << "BFS(" << start_x << ", " <<start_y << ")수행\n";
	vector<pair<int, int>> direction{ {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
	int current_x, current_y, next_x, next_y;
	int d_size = direction.size(), i;
	vector<pair<int, int>> pop;
	queue <pair<int, int>> q;
	int link = 1;

	q.push({ start_x, start_y });
	visited[start_y][start_x] = true;
	pop.push_back({ start_x, start_y });
	while (!q.empty())
	{
		current_x = q.front().first;
		current_y = q.front().second;
		q.pop();
		for (i = 0; i < d_size; i++)
		{
			next_x = current_x + direction[i].first;
			next_y = current_y + direction[i].second;
			if ((next_x >= 0 && next_x < W) && (next_y >= 0 && next_y < H)
				&& (board[next_y][next_x] == color)
				&& (visited[next_y][next_x] == false))//보드 범위 내에 존재하고, 색이 같고, 방문한적 없는 경우
			{
				visited[next_y][next_x] = true;//방문하고
				q.push({ next_x, next_y });
				pop.push_back({next_x, next_y});//일단 추가하고
				link++;//연결개수 증가하고
			}
		}
	}
	//cout << "link = " << link << "\n";
	if (link >= 4)//뿌요뿌요 갯수가 4개 이상일 경우 모든 뿌요뿌요 폭파
	{
		*continue_puyopuyo = true;//폭파 발생했으니 보드판 최신화 필요
		//*count += 1;//폭파 갯수 증가	
		//cout << "count = " << *count << "\n";
		for (i = 0; i < pop.size(); i++)
		{
			board[pop[i].second][pop[i].first] = '.';//연결된 뿌요뿌요 모두 연쇄폭파!
		}
	}

	return;
}

void find_answer()
{
	int count = 0;
	int i, j;
	bool continue_puyopuyo;
	/*
	* 1. 현재 있는 뿌요뿌요 중 터뜨릴 수 있는 모든 뿌요뿌요를 폭파
	* 2. visited를 초기화
	* 3. 뿌요뿌요를 내릴 수 있는 경우 내리기
	* 4. 반복
	*/

	while (1)//모든 뿌요뿌요들이 더이상 연쇄가 없을때까지 반복
	{
		continue_puyopuyo = false;
		for (i = 0; i < H; i++)
		{
			for (j = 0; j < W; j++)
			{
				if (board[i][j] != '.' && visited[i][j] == false) //해당위치에 뿌요뿌요가 존재하고, 방문한적이 없을 경우
				{
					BFS(j, i, board[i][j], /*&count,*/ &continue_puyopuyo);
				}
			}
		}
		if (continue_puyopuyo)//최신화 필요한 경우
		{
			count++;//여기 추가: 한 턴에 여러개가 터져도 count는 한번만 올라간다?
			reinit_board();
			reinit_visited();
		}
		else//뿌요뿌요가 터진 게 없으면 중단
		{
			break;
		}
	}

	cout << count << "\n";
}

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

	input_puyopuyo();
	find_answer();

	return 0;
}