[백준/BOJ] 백준 2638번 : 치즈

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

2638번: 치즈

 

주어진 모눈종이를 둘러싸는 바깥의 행과 열이 추가된 공간이 있다고 가정하고, 그 공간의 위치들부터 공기가 시작되어 공기가 전파되는 위치를 표시해 놓고, 각 치즈의 위치와 접촉하는 부분에서 공기가 전파된 위치가 2개 이상 있는지 확인하는 방법으로 치즈가 지금 녹는지 확인해서 문제를 해결했다.

 

코드

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

int n, m;
int board[105][105];
int total_cheese = 0;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

bool remove_check() {

	vector<vector<int>> air_check(105, vector<int>(105, 0)); //외부 공기 위치 체크
	queue<pair<int, int>> q;

	//외부 초기 공기 위치 넣기
	for (int j = 0; j <= m + 1; j++) {
		air_check[0][j] = 1;
		q.push(make_pair(0, j));

		air_check[n + 1][j] = 1;
		q.push(make_pair(n + 1, j));
	}
	for (int i = 1; i <= n; i++) {
		air_check[i][0] = 1;
		q.push(make_pair(i, 0));

		air_check[i][m + 1] = 1;
		q.push(make_pair(i, m + 1));
	}

	while (!q.empty()) {
		pair<int, int> here = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);

			if (there.first >= 0 && there.first <= n + 1 && there.second >= 0 && there.second <= m + 1 && board[there.first][there.second] == 0 && air_check[there.first][there.second] == 0) {
				air_check[there.first][there.second] = 1;
				q.push(there);
			}

		}
	}

	//각 치즈가 외부공기와 2변 이상 접촉하는지 확인
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			pair<int, int> here = make_pair(i, j);

			if (board[here.first][here.second] == 1) { //치즈일때
				int cnt = 0;

				for (int dir = 0; dir < 4; dir++) {
					pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);

					if (air_check[there.first][there.second] == 1) {
						cnt++;
					}
				}

				if (cnt >= 2) {
					board[here.first][here.second] = 0;
					total_cheese--;
				}
			}

		}
	}

	if (total_cheese == 0) {
		return true;
	}

	return false;
}

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

	cin >> n >> m;

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

			board[i][j] = input;

			if (input == 1) {
				total_cheese++;
			}
		}
	}

	int result = 0;

	while (1) {
		result++;

		if (remove_check()) {
			break;
		}
	}

	cout << result;

	return 0;
}