백준2636 - 치즈

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

2636번: 치즈

bfs를 활용하여 공기인 부분을 찾고 현재 위치에서 네 방향을 탐색하여 공기와 맞닫는 치즈 면적을 날리는 문제였다.

 

공기와 맞닫는 면적을 구하던 중 문제가 되었던 부분이 있었다. 바로 치즈에 구멍이 뚫린 경우 였다. 이 경우는 0과 2로 표현하였다. 처음 입력시에는 모든 구멍과 공기인 부분을 0으로 매웠다. 그리고 (1, 1)번지부터 탐색을 하여 순수한 공기인 부분과 공기와 맞닿은 구멍 부분은 2로 바꾸었다. (1, 1)번지부터 탐색한 이유는 제일 바깥쪽 테두리 부분은 공기로 매운다고 문제에서 주었기 때문이다.

 

공기와 닿는 부분을 2로 다 채웠으면 단계마다 남아있는 치즈의 갯수를 치즈가 한 개도 없는 순간까지 벡터에 저장하였다. 사라지는 치즈를 구하는 방법으로는 현재 치즈 위치에서 4방향으로 공기와 닿는 부분이 존재하면 그 부분을 사라지게 하였다. 중요한 점은 찾는 즉시 공기로 바꾸면 다음 바로 아래 치즈에 영향을 미치기 때문에 치즈의 위치를 따로 저장해 두었다가 삭제하였다.

 

최종적으로 벡터에 저장된 값에서 뒤에서 두번째가 모든 치즈가 사라지기 바로 직전에 치즈 갯수이다.

 

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

int cnt = 0; //처음 치즈 갯수
int time = 0; //공기에 맞닫는 시간
int ans = 0; //답

int m, n; // 좌표크기

int mat[MAX][MAX]; //좌표 정보

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

vector<int> v; //여태까지 지웠던 치즈의 갯수

void bfs() {
	bool visit[MAX][MAX] = { false, }; //모든 공간 방문여부 false로 초기화
	queue<pair<int, int>> q; //공기 좌표를 담을 공간

	q.push(pair<int,int>(1, 1)); //처음 위치를 (1, 1)로 설정하여 
	mat[1][1] = 2; //처음 공기인 부분 2로 바꾸기
	visit[1][1] = true; //처음 위치

	while (!q.empty()) { //현재 공기인 부분의 좌표가 다 사라질 때까지 반복
		//현재 좌표를 추출하고 큐에서 삭제
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

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

			//현재 위치가 유효한 범위이고 공기나 구멍을 만난다면
			if (1 <= nx && nx <= m && 1 <= ny && ny <= n && !visit[nx][ny] && (mat[nx][ny] == 0 || mat[nx][ny] == 2)) { 
				if (mat[nx][ny] == 0) { //현재 이동하려는 곳이 구멍이면
					mat[nx][ny] = 2; //공기로 바꾼다.
				}
				visit[nx][ny] = true; //방문처리
				q.push(pair<int, int>(nx, ny)); //이동하려는 곳의 위치를 큐에 삽입
			}
		}
	}
	
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

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

	v.push_back(cnt); //현재 치즈의 갯수를 제일 처음으로 삽입

	while (cnt) { //치즈가 모두 사라지기 전까지 치즈 소멸 작업을 반복
		bfs(); //공기인 부분 찾기, 구멍에서 공기로 바뀌는 부분 찾기
		time++; //총 걸린시간 증가
		queue < pair<int, int>> q; //치즈 위치를 저장할 공간

		//좌표 안에 모든 범위를 탐색
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				if (mat[i][j] == 1) { //현재 위치가 치즈이고
					if (mat[i - 1][j] == 2 || mat[i + 1][j] == 2 || mat[i][j + 1] == 2 || mat[i][j - 1] == 2) { //4방향 중 어느 한 방향이라도 공기와 닿으면
						cnt--; //치즈가 사라지고
						q.push(pair<int, int>(i, j)); //현재 치즈 위치를 큐에 삽입
					}
				}
			}
		}

		//큐가 빌 때까지 치즈 위치를 공기로 전환
		while (!q.empty()) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();

			mat[x][y] = 2;
		}

		v.push_back(cnt); //현재 치즈 갯수 삽입
	}
	
	//걸린 시간과 모든 조각이 사라지기 직전 치즈 갯수 출력
	cout << time << '\n';
	cout << v[v.size() - 2];
}