[백준 C++] 2638 치즈 - 너비우선탐색

2638번: 치즈

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

int N, M;
bool Cheeze[100][100];

const int DX[4] = { -1, 0, 1, 0 };
const int DY[4] = { 0, -1, 0, 1 };

queue<pair<int, int>> SQ;
bool Visited[100][100];
int Air[100][100];

void BFS()
{
	memset(Visited, false, sizeof(Visited));
	memset(Air, 0, sizeof(Air));

	Visited[0][0] = true;
	SQ.emplace(0, 0);
	while (!SQ.empty())
	{
		int R = SQ.front().first;
		int C = SQ.front().second;
		SQ.pop();
		
		for (int i = 0; i < 4; ++i)
		{
			int NR = R + DY[i];
			int NC = C + DX[i];

			if (NR < 0 || NR > N - 1
				|| NC < 0 || NC > M - 1
				|| (!Cheeze[NR][NC] && Visited[NR][NC]))
			{
				continue;
			}

			if (Cheeze[NR][NC])
			{
				++Air[NR][NC];
			}
			else
			{
				Visited[NR][NC] = true;
				SQ.emplace(NR, NC);
			}
		}
	}
}

void DeleteCheeze()
{
	BFS();

	for (int i = 1; i < N - 1; ++i)
	{
		for (int j = 1; j < M - 1; ++j)
		{
			if (Air[i][j] >= 2)
			{
				Cheeze[i][j] = false;
			}
		}
	}
}

bool HaveCheeze()
{
	for (int i = 1; i < N - 1; ++i)
	{
		for (int j = 1; j < M - 1; ++j)
		{
			if (Cheeze[i][j])
			{
				return true;
			}
		}
	}

	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> Cheeze[i][j];
		}
	}

	int Time = 0;
	while (HaveCheeze())
	{
		DeleteCheeze();
		++Time;
	}

	cout << Time;
}

---

 

매 시간마다 공기에 노출된 치즈가 녹는 상황을 구현하는 문제입니다.

 

공기에 노출된 치즈 칸을 결정하는 조건은 두 개 이상의 외부 빈칸과 접촉할 때입니다.

이 말은 즉 내부에 존재하는 빈칸과는 접촉해도 개수에 카운팅 되지 않음을 뜻합니다.

 

따라서 매 시간마다 두 개 이상의 외부의 빈칸과 접촉한 치즈 칸을 골라서 해당 칸을 빈칸으로 만들어주어야 합니다.

이 때 종이의 가장자리는 무조건 빈칸(외부)이므로,

0,0 칸부터 너비 우선 탐색을 시작해서 탐색 큐에 인접한 빈칸(무조건 외부임)을 계속 넣어줍니다.

그리고 탐색 큐의 각 칸들이 인접한 치즈 칸을 만났을 때마다 해당 치즈 칸의 카운팅을 늘려줍니다.

탐색을 종료하고나면, 종이에서 2개 이상 카운팅된 치즈 칸들을 모두 빈칸으로 만들어주면 됩니다.