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

2638번: 치즈

cpp

#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개 이상 카운팅된 치즈 칸들을 모두 빈칸으로 만들어주면 됩니다.