[c++/백준] 2636번: 치즈

문제 링크

2636번: 치즈

풀이

BFS로 푸는 문제.

1. 먼저 바깥쪽에 있는 치즈를 체크하기 위해 항상 값이 0인 (0,0)부터 체크한다.
2. 여느 BFS와 같이 queue로 푸는데, 체크해줘야 할 것은 0인 값과 1인 값을 다르게 처리해야 한다.
   2-1. 0인 값: 공기이므로 퍼짐 -> queue에 push
   2-2. 1인 값: 치즈이므로 안퍼짐 -> 그 시간에 녹는 치즈 개수인 cheese를 갱신해주고, 치즈가 녹으니 0으로 값을 갱신해준다. 녹는 치즈가 있다면 flag=true로 설정해준다. 이건 치즈가 다 녹을 때까지 계속해서 반복해주는데에 break를 걸어준다.
3. 녹는 치즈가 있다면(flag==true) 마지막 녹은 치즈 개수인 lastCheese에 cheese 값을 갱신한다.
4. 2-2에서 설명했듯이 flag==true일 때까지 반복하고, 시간 체크를 위한 time을 갱신해준다.

코드

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

using namespace std;

int n, m;
vector<vector<int>> board;

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

int lastCheese;

bool BFS(int y, int x)
{
	vector<vector<int>> visit(n, vector<int>(m));
	queue<pair<int, int>> q;

	q.push({y,x});
	visit[y][x] = 1;

	bool flag = false;

	int cheese = 0;
	while (!q.empty())
	{
		int curY = q.front().first;
		int curX = q.front().second;
		q.pop();
		for (int i = 0;i < 4;i++)
		{
			int ny = curY + dy[i];
			int nx = curX + dx[i];
			if (ny >= n || ny < 0 || nx >= m || nx < 0) continue;
			if (visit[ny][nx]) continue;
			visit[ny][nx] = 1;
			if (board[ny][nx] == 0) q.push({ ny,nx });
			else
			{
				cheese++;
				board[ny][nx] = 0; //바깥쪽 치즈가 녹음
				flag = true;
			}
		}
	}
	
	if (flag) lastCheese = cheese;
	return flag;
}

int main(void)
{
	cin >> n >> m;

	board.resize(n, vector<int>(m));
	
	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < m;j++)
		{
			cin >> board[i][j];
		}
	}

	int time = 0;
	while (1)
	{
		if (BFS(0, 0)) time++;
		else break;
	}
	
	cout << time << endl;
	cout << lastCheese << endl;

	return 0;
}