[BOJ / 플러드필 BFS] 2638 치즈

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

2638번: 치즈

 

2638 치즈

알고리즘 : 플러드필 / BFS

바깥공기와 치즈, 안쪽 공기를 나누어 표기하고 첫 큐를 이용해 바깥공기를 처리, 공기에 맡닿은 치즈를 골라주고,

두번째 큐를 이용하여 다음 시간대에 녹을 치즈를 골라줍니다. 그렇게 골라서 만약 바깥공기와 안쪽 공기가 닿을 경우 첫 큐를 이용하여 처음과 같은 처리를 다시 이용해 주되, 메모이제이션을 통해 중복된 연산을 하지 않도록 합니다.

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

도 비슷한 문제이니 같이 풀어보시면 좋을 것 같습니다.

 

 

 

 

 

 

 

 

< CODE >

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

using namespace std;

#define MAX 105

struct forQ
{
	int y;
	int x;
	int year;
};

int f[MAX][MAX];
int condi[MAX][MAX]; // -1 out 1 cheese 0 in the cheese
int cnt[MAX][MAX];
bool visited[MAX][MAX];
queue<pair<int, int>> q;
queue<forQ> q2;

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

int n, m;

bool isSafe(pair<int,int> p)
{
	if (p.first > 0 && p.second > 0 && p.first <= n && p.second <= m && !visited[p.first][p.second])
		return true;
	return false;
}

void checkAir(int year)
{
	while (!q.empty())
	{
		pair<int, int> cur = q.front(); q.pop();

		condi[cur.first][cur.second] = -1;

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> to = { cur.first + dy[i], cur.second + dx[i] };

			if (isSafe(to))
			{
				if (f[to.first][to.second] == 0)
				{
					visited[to.first][to.second] = true;
					q.push(to);
				}
				else if (condi[to.first][to.second] == 1)
				{
					cnt[to.first][to.second]++;

					if (cnt[to.first][to.second] >= 2 && condi[to.first][to.second] == 1)
					{
						cnt[to.first][to.second] = 0;
						condi[to.first][to.second] = -1;
						q2.push({ to.first, to.second, year });
					}
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int result = 0;

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> f[i][j];

			if (f[i][j] == 1)
				condi[i][j] = 1;
		}
	}

	q.push({ 1,1 });

	visited[1][1] = true;

	checkAir(1);

	while (!q2.empty())
	{
		forQ cur = q2.front(); q2.pop();

		result = cur.year;

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> to = { cur.y + dy[i], cur.x + dx[i] };

			if (condi[to.first][to.second] == 1)
			{
				cnt[to.first][to.second]++;

				if (cnt[to.first][to.second] >= 2)
				{
					cnt[to.first][to.second] = 0;
					condi[to.first][to.second] = -1;
					q2.push({ to.first, to.second, cur.year + 1 });
				}
			}
			else if (condi[to.first][to.second] == 0)
			{
				q.push(to);
				visited[to.first][to.second] = true;
				checkAir(cur.year + 1);
			}
		}	
	}
	
	cout << result << '\n';

	return 0;
}

시간 : 0ms

 

태그 : #BOJ 치즈 #백준 치즈 #2638 치즈 #플러드필