[BOJ / BFS] 2638 치즈

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

2638번: 치즈

 

2638 치즈

알고리즘 : 플러드필, BFS, 메모이제이션

1,1은 무조건 바깥 공기이므로 1,1 공기로 플러드필을 통해 바깥 공기들을 구분합니다. 이 과정 중 다음 세대에 녹을 치즈를 판별하고, ( 녹을 치즈 구분 / 안쪽 공기 구분 )을 반복하며 문제를 해결합니다.

 

 

 

< CODE >

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

using namespace std;

#define MAX 105

int arr[MAX][MAX];
int cnt[MAX][MAX];
bool visited[MAX][MAX];

struct Point {
	int y;
	int x;
};

int n, m;

queue<Point> q;
queue<Point> q2;
vector<Point> nextMelt;

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

bool Safe(Point p){
	if (p.y > 0 && p.x > 0 && p.y <= n && p.x <= m)
		return true;
	return false;
}

void bfs(Point p) {
	q.push(p);
	visited[p.y][p.x] = true;

	while (!q.empty()) {
		Point cur = q.front(); q.pop();

		for (int i = 0; i < 4; i++) {
			int dY = dy[i] + cur.y;
			int dX = dx[i] + cur.x;

			if (Safe({ dY,dX })){
				if (!visited[dY][dX] && arr[dY][dX] == 0) {
					visited[dY][dX] = true;
					q.push({ dY,dX });
				}
				else if (arr[dY][dX] == 1 && cnt[dY][dX] < 2)
				{
					cnt[dY][dX]++;

					if (cnt[dY][dX] == 2)
						nextMelt.push_back({ dY,dX });
				}
			}
		}
	}
}

int solve() {
	int answer = 0;

	while (!nextMelt.empty()) {
		for (int i = 0; i < nextMelt.size(); i++) {
			q2.push(nextMelt[i]);
		}

		nextMelt.clear();

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

			for (int i = 0; i < 4; i++) {
				int dY = dy[i] + cur.y;
				int dX = dx[i] + cur.x;

				if (Safe({ dY,dX })) {
					if (!visited[dY][dX] && arr[dY][dX] == 0) {
						// 안쪽 공기인 경우
						bfs({ dY,dX });
					}
					else if (arr[dY][dX] == 1 && cnt[dY][dX] < 2)
					{
						cnt[dY][dX]++;

						if (cnt[dY][dX] == 2)
							nextMelt.push_back({ dY,dX });
					}
				}
			}
		}

		answer++;
	}

	return answer;
}

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


	cin >> n >> m;

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

	bfs({ 1,1 });
	cout << solve() << '\n';
}

시간 : 0ms

 

태그 : #2638 치즈 #BOJ 치즈