백준 2636 c++

오랜만에 BFS 문제를 풀어보았다.
처음 풀이할 때 포기하고 다시 도전해 본 문제다.
첫 풀이 때는 치즈를 시작으로 BFS를 돌리려 해서 치즈 가운데 구멍을 해결하지 못해서 포기했다.

문제를 다시 잘 읽어보고 배열의 가장자리는 전부 공백으로 치기 때문에 (0,0)에서 BFS를 시작하면 치즈 구멍을 신경 안써도 된다고 생각했다.

풀이 자체는 무난하게 성공했지만, 치즈 개수를 확인 로직을 각 BFS마다 전체 배열을 순회하는 방식으로 해서 불필요한 순회가 많이 발생할거 같았다. 그래서 최초 입력시에 치즈 개수를 받고 (전달된 치즈 개수 - 녹인 치즈 개수)로 다음 치즈 개수를 파악했다.

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

using namespace std;

void input_data(vector<vector<bool>>& cheese, int *init_cheese)
{
	//cout << "\ninput_data()\n";
	int garo, sero, i, j, count = 0;
	bool temp;

	cin >> sero >> garo;
	cheese.resize(sero, vector<bool>(garo));
	for (i = 0; i < sero; i++)
	{
		for (j = 0; j < garo; j++)
		{
			cin >> temp;
			cheese[i][j] = temp;
			if (temp)
			{
				count++;
			}
		}
	}
	*init_cheese = count;

	//cout << "\n입력결과\n";
	//for (i = 0; i < sero; i++)
	//{
	//	for (j = 0; j < garo; j++)
	//	{
	//		cout << cheese[i][j] << " ";
	//	}
	//	cout << "\n";
	//}

	return;
}

void BFS(vector<vector<bool>>& cheese, int *cheese_count, int init_cheese)
{
	//cout << "\nBFS()\n";
	int sero = cheese.size(), garo = cheese[0].size(), count = 0;
	vector<vector<bool>> visited(sero, vector<bool>(garo, 0));
	int i, j, current_x, current_y, next_x, next_y;
	queue <pair<int, int>> q;
	vector<pair<int, int>> direction{ {1, 0},{0, 1},{-1, 0},{0, -1} };

	q.push({ 0, 0 });
	visited[0][0] = true;
	while (!q.empty())
	{
		current_x = q.front().first;
		current_y = q.front().second;
		q.pop();
		for (i = 0; i < direction.size(); i++)
		{
			next_x = current_x + direction[i].first;
			next_y = current_y + direction[i].second;
			if ((next_x >= 0 && next_x < garo) && (next_y >= 0 && next_y < sero) && !visited[next_y][next_x])// 범위 내에 있고, 방문한 적 없음
			{
				if (cheese[next_y][next_x])//치즈인 경우
				{
					cheese[next_y][next_x] = false;//치즈칸 녹이기
					visited[next_y][next_x] = true;//방문 처리
					count++;//녹인 치즈 개수 증가
					//큐에는 안 들어가
				}
				else//빈 공간인 경우
				{
					q.push({ next_x, next_y });//큐에 넣기
					visited[next_y][next_x] = true;//방문하기
					//치즈칸 녹일 필요 없음
				}
			}
		}
	}

	////cout << "치즈 녹이기 BFS() 결과\n";
	//for (i = 0; i < sero; i++)//치즈 개수 확인 //이렇게 하면 매번 순회를 한번 더 하게 되는데...
	//{
	//	for (j = 0; j < garo; j++)
	//	{
	//		if (cheese[i][j])
	//		{
	//			count++;
	//		}
	//		//cout << cheese[i][j] << " ";
	//	}
	//	//cout << "\n";
	//}
	*cheese_count = init_cheese - count;//최초 치즈 개수 - 녹인 치즈 개수 = 현재 남은 치즈 개수

	return;
}

void find_answer(vector<vector<bool>>& cheese, int init_cheese)
{
	//cout << "\nfind_anwser()\n";
	int time_count = 0;//모두 녹아서 없어지는 데 걸리는 시간
	int cheese_count;//모두 녹기 한 시간 전 남은 치즈칸 개수
	//int remained_cheese = init_cheese; //이전 치즈 칸 개수 저장

	while (1)
	{
		BFS(cheese, &cheese_count, init_cheese);
		if (cheese_count == 0)//이번 순회로 치즈가 다 녹아 사라지면?
		{
			time_count++;
			break;
		}
		else//이번 순회 후에도 치즈가 남아 있다면
		{
			init_cheese = cheese_count;
			time_count++;
		}
		//cout << "cheese_count : " << cheese_count << "\n";
		//cout << "remained_cheese : " << remained_cheese << "\n";
		//cout << "time_count : " << time_count << "\n";
	}
	cout << time_count << "\n" << init_cheese << "\n";

	return;
}

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

	vector<vector<bool>> cheese;
	int init_cheese = 0;

	input_data(cheese, &init_cheese);
	find_answer(cheese, init_cheese);

	return 0;
}