백준2638 - 치즈

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

2638번: 치즈

어제 풀었던 치즈 문제에서 조금 변형한 형태이다. 전과 다른 점은 두 변 이상이 공기와 공유되어야 치즈가 사라진다. 이점만 고려한다면 전에 풀었던 2636번 치즈 문제(https://www.acmicpc.net/problem/2636)와 풀이가 같다. 

#include <iostream>
#include <queue>
#define MAX 101
using namespace std;

int mat[MAX][MAX]; //좌표 정보
int N, M; //치즈의 크기 (N * M)

int cnt = 0; //치즈 갯수
int time = 0; //걸린 시간

//상하좌우
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

//치즈 구멍을 공기로 바꾸는 작업, bfs를 활용
void air() {
	bool visit[MAX][MAX] = { false, };
	queue<pair<int, int>> q;

	mat[1][1] = 2; //1,1를 시작으로 탐색, 공기로 설정
	visit[1][1] = true; //방문 처리
	q.push(pair<int, int>(1, 1)); //시작점을 큐에 삽입

	while (!q.empty()) {
		//원소 추출하고 제거
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) { //상하좌우 이동
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			//유효한 좌표 범위이고 방문을 안한 공간이며 치즈 구멍이거나 공기인 경우를 선택
			if (1 <= nx && nx <= N && 1 <= ny && ny <= M && !visit[nx][ny] && (mat[nx][ny] == 0 || mat[nx][ny] == 2)) {
				if (mat[nx][ny] == 0) { //치즈 구멍이면 
					mat[nx][ny] = 2; //2로 변환
				}
				q.push(pair<int, int>(nx, ny)); //가려고 하는 위치를 큐에 삽입
				visit[nx][ny] = true; //가려고 하는 위치 방문처리
			}
		}
	}
}

//치즈가 공기와 닿는 부분을 체크(좌우, 좌상, 좌하, 상우, 상하, 우하)
//두 변이상 공기와 공유하지 않는다면 false, 두 변이상 공기와 공유하면 true
//유효범위로 탐색
bool change(int x, int y) {
	if (1 <= x - 1 && x + 1 <= N && 1 <= y - 1 && y + 1 <= M) { 
		if (mat[x - 1][y] == 2 && mat[x + 1][y] == 2) {
			return true;
		}
		else if (mat[x - 1][y] == 2 && mat[x][y + 1] == 2) {
			return true;
		}
		else if (mat[x - 1][y] == 2 && mat[x][y - 1] == 2) {
			return true;
		}
		else if (mat[x + 1][y] == 2 && mat[x][y + 1] == 2) {
			return true;
		}
		else if (mat[x + 1][y] == 2 && mat[x][y - 1] == 2) {
			return true;
		}
		else if (mat[x][y + 1] == 2 && mat[x][y - 1] == 2) {
			return true;
		}
		else {
			return false;
		}
	}
}

int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> mat[i][j];
			if (mat[i][j] == 1) { //치즈면
				cnt++; //치즈갯수 증가
			}
		}
	}

	//모든 치즈가 사라질 때까지 진행
	while (cnt) {
		time++; //걸린 시간 증가
		air(); //공기로 변환되는 공간 모두 공기로 변환하기

		queue<pair<int, int>> cheeze; //삭제할 치즈

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (mat[i][j] == 1) { //치즈면
					bool check = change(i, j); //공기와 닿는 부분 2개 이상인지 체크
					if (check) { //두 개이상 닿으면
						cheeze.push(pair<int, int>(i, j)); //삭제할 치즈로 선정
					}
				}
			}
		}

		//삭제할 치즈 모두 공기로 변환
		while (!cheeze.empty()) {
			int x = cheeze.front().first;
			int y = cheeze.front().second;
			cheeze.pop();

			mat[x][y] = 2; //치즈를 공기로 변환
			cnt--; //치즈 갯수 줄이기
		}
	}

	cout << time;
}