Baekjoon2638-치즈

백준 사이트 2638 - 치즈 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

BFS문제입니다.
시간이랑 메모리가 넉넉한 편은 아니지만 어렵지 않습니다.
백준에서는 Gold4의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 비슷한 문제로 치즈 2가 있습니다. 그것과 다른점은 면 2개를 세줘야한다는 점이 다릅니다.
• DFS로 분류되어있지만 BFS로 풀었습니다.
• 메모리를 줄이기 위해 맵을 bool 형태로 만들고 하나의 while문에 끝내려고 노력했습니다.
• 어차피 0,0부터 돌면서 BFS를하든 DFS를 하든 안쪽 공기는 못 도므로 방문 안한 공기는 내부 공기로 취급했습니다.
• 한번 돌았을 때 밖으로 노출되는 공기들이 새로 생기므로 다시 한번 돌아주는 방법으로 했습니다.

---

5. code

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

const int MAX = 101;

bool MAP[MAX][MAX] = { false, };
bool v[MAX][MAX] = { false, };

int n, m;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int cheese = 0;
int hour = 0;

void printMAP()
{
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
			cout << MAP[i][j] << " ";
		cout << '\n';
	}
	cout << '\n';
}

void Input()
{
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> MAP[i][j];
			if (MAP[i][j])
				++cheese;
		}
	}
}

void Solve()
{
	queue<pair<int,int>> q;
	while (cheese != 0)
	{
		memset(v, false, sizeof(v));
		q.push(make_pair(0, 0));

		//먼저 외부 공기들은 다 check 상태로 만듬
		while (!q.empty())
		{
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			for (int k = 0; k < 4; ++k)
			{
				int newX = x + dx[k];
				int newY = y + dy[k];
                //공기 이면서 한번도 안돈 공기
				if (0 <= newX && newX < n && 0 <= newY && newY < m && MAP[newX][newY] == false && v[newX][newY] == false)
				{
					v[newX][newY] = true;
					q.push(make_pair(newX, newY));
				}
			}
		}
		//공기들은 다 check로 바꿈 이제 돌면서 치즈삭제

		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				if (MAP[i][j] == true)
				{
					//상하좌우검사
					int count = 0;
					for (int k = 0; k < 4; ++k)
					{
						int newX = i + dx[k];
						int newY = j + dy[k];
						if (0 <= newX && newX < n && 0 <= newY && newY < m && v[newX][newY] == true && MAP[newX][newY]==false)// 즉 공기이고 이미 외각 쪽 공기라면
						{
							++count;
						}
					}
					if (count >= 2)//녹일 치즈
					{
						MAP[i][j] = false;
						--cheese;
					}
				}
			}
		}
		
		++hour;
		//printMAP();
	}
	cout << hour;
}

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

	Input();
	Solve();
}

---

6. 후기

처음에는 매번 공기를 찾아 BFS를 하는게 시간상의 손해인 것 같았다.
그래서 한번에 처리하려고 하다가 무한루프에 빠져 틀렸다.

8 9
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 1 0
0 1 0 1 1 1 0 1 0
0 1 0 0 1 0 0 1 0
0 1 0 1 1 1 0 1 0
0 1 1 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0

이 예제를 돌려서 고쳤다.