Baekjoon2636-치즈

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

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

BFS문제입니다.
정답률이 높은데 예외가 없어서 그런것 같습니다.
이 문제가 만약 정사각형판이 주어지지 않았다면 난이도가 더욱 많이 올라갔을거라 생각합니다. 이유는 밑에 써보겠습니다.
백준에서는 Gold5난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 기존 문제와 다른 것은 종료 전의 치즈 갯수를 기억해야한다는 것입니다. 알아두면 구현은 어렵지 않습니다.
• queue에 넣고 한번에 처리하는 문제도 있는데 이문제는 치즈의 “겉 부분”만 제거해주면 되기에 한번에 처리안해도 됩니다.
• BFS를 돌 때 0,0부터 돌아야하나 생각이 있었습니다.
  • 정사각형판이 ‘외부’로 판단하고 문제를 출제하여 0,0부터 돌아도 상관없습니다. 만약 판이 없었다면 공기가 통하는 부분을 따로 찾아줘야 했을 것입니다..
• 종합해보면 BFS를 0,0부터 돌면서 치즈를 만나면 공기로 바꿔버리면서 BFS 도는 횟수(day)와 치즈의 갯수를 비교하면 문제는 풀립니다.

---

5. code

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

const int MAX = 101;

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

int result = 0;
int Ccount = 0;
int day = 0;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

//없어도됨.
void print()
{
	for (int i = 0; i < row; ++i)
	{
		for (int j = 0; j < col; ++j)
			cout << MAP[i][j] << " ";
		cout << '\n';
	}
}

void Input()
{
	cin >> row >> col;

	for (int i = 0; i < row; ++i)
	{
		for (int j = 0; j < col; ++j)
		{
			cin >> MAP[i][j];
			if (MAP[i][j] == 1)
				++Ccount;
		}
	}
}

void Solve()
{
	queue<pair<int, int>> q;

	while (Ccount != 0)
	{
		day++;
		result = Ccount;
		memset(v, false, sizeof(v));
		q.push(make_pair(0, 0));
		while (!q.empty())
		{
			int airx = q.front().first;
			int airy = q.front().second;
			q.pop();
			for (int k = 0; k < 4; ++k)
			{
				int newAx = airx + dx[k];
				int newAy = airy + dy[k];
				if (0 <= newAx && newAx < row && 0 <= newAy && newAy < col && v[newAx][newAy] == false)
				{
					if (MAP[newAx][newAy] == 1)//치즈인경우
					{
						MAP[newAx][newAy] = 0;
						--Ccount;
					}
					else //공기인경우
						q.push(make_pair(newAx, newAy));
					v[newAx][newAy] = true;
				}
			}
		}
	}
}

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

	Input();
	Solve();
	cout << day << '\n' << result << '\n';
}

---

6. 후기

이제 골드5 난이도의 BFS문제는 한 10분 정도 생각하고 바로바로 푸는 것 같다. 속도가 늘었다.
좋긴한데 더 어려운 난이도에 대한 겁이 아직도 난다.