백준 - 치즈 (2638) [C++]

이 문제는 bfs를 이용해서 푸는 문제이다.

 

입력으로 주어지는 2차원 배열이 최대 100 x 100 이므로 O(N^2) 알고리즘일 경우 최대 10,000번의 반복을 수행할 수 있다.

모눈종이의 가장자리에는 치즈가 놓이지 않기 때문에, 치즈가 아무리 많아도 98 x 98 크기를 넘을 수 없다. 각 가장자리부터 한 반복문 당 한 겹씩 사라지므로 충분히 시간 안에 풀 수 있다.

 

가장 핵심은 외부 공기와 내부 공기를 구분하는 것인데, 이를 위해 가장자리에는 치즈가 놓이지 않는다는 가정을 사용했다. 이는 가장자리는 무조건 외부 공기라는 말이 된다. 따라서 (0,0) 에서부터 bfs를 시작하여 치즈를 만나면 멈추는 방식으로 구현하면 외부 공기들을 알아낼 수 있다.

 

그 다음 알아낸 외부 공기 2차원 벡터를 이용하여 치즈를 없애고, 이를 반복하여 횟수를 알아내면 정답을 맞출 수 있다.

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

#define MAX 100

int N, M;
vector<vector<int>> cheeze;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };

void input() {
	cin >> N >> M;
	cheeze = vector<vector<int>>(N, vector<int>(M));
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> cheeze[y][x];
		}
	}
}

bool isEnd() {
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (cheeze[y][x] == 1) {
				return false;
			}
		}
	}
	return true;
}

bool inRange(int y, int x) {
	if (0 <= y && y < N && 0 <= x && x < M) {
		return true;
	}
	return false;
}

vector<vector<bool>> bfs(int startY, int startX) {
	vector<vector<bool>> visited(N, vector<bool>(M, false));
	queue<pair<int, int>> q;
	visited[startY][startX] = true;
	q.push({ startY, startX });

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (inRange(ny, nx) && !visited[ny][nx] && cheeze[ny][nx] == 0) {
				visited[ny][nx] = true;
				q.push({ ny, nx });
			}
		}
	}

	return visited;
}

void removeCheeze(vector<vector<bool>>& outer) {
	vector<vector<int>> result = cheeze;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (cheeze[y][x] == 0) {
				continue;
			}

			int airCnt = 0;

			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];

				if (!inRange(ny, nx)) {
					continue;
				}

				if (cheeze[ny][nx] == 1) {
					continue;
				}

				if (cheeze[ny][nx] == 0 && outer[ny][nx]) {
					airCnt++;
				}
			}

			if (airCnt >= 2) {
				result[y][x] = 0;
			}
		}
	}

	cheeze = result;
}

int solve() {
	if (isEnd()) {
		return 0;
	}

	int result = 0;
	while (true) {
		result++;
		// find outer air
		vector<vector<bool>> outerAir = bfs(0, 0);
		removeCheeze(outerAir);

		if (isEnd()) {
			return result;
		}
	}
	return -1;
}

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

	input();
	cout << solve() << '\n';

	return 0;
}