[백준 2638] 치즈

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

2638번: 치즈

 

2차원 지도에서 특정조건을 만족하는 칸부터 상태가 변하며 모든 칸의 상태가 변할 때까지 걸리는 시간을 출력하는 문제이다. 전형적인 그래프 탐색에 구현이 붙은 문제이다.

 

---

1시간이 지날때마다 지도에서 몇 가지를 체크하는데,

1. 외부 공기.
   -  치즈 내부에도 공기가 있는데 내부 공기 칸의 테두리의 치즈가 녹은 경우, 해당 공기 칸을 외부 공기로 바꿔줘야 한다. 
   - airCheck()로 구현.
2. 녹는 치즈 칸.
   - 외부 공기와 2칸 이상 접촉하고 있는 치즈의 경우, 1시간 후 녹여야 한다.
   - meltPointCheck()에서 meltPoint[][]에 1시간이 지날 때마다 녹여야 하는 치즈 칸을 저장하여 meltCheese()로 녹인다.
3. 녹일 수 있는 치즈 존재 여부.
   - 지도에서 더 이상 녹일 수 있는 치즈가 존재하는 지 확인해야 한다.
   - meltCheese()의 return값을 통해 판별한다.

 

 

 

#include <iostream>
#include <cstring>
using namespace std;

int x_dir[] = { 0,1,0,-1 };
int y_dir[] = { 1,0,-1,0 };
int n, m, ans;
int map[101][101];
bool air[101][101];
bool meltPoint[101][101];

void airCheck(int y, int x) {
	air[y][x] = true;
	for (int i = 0; i < 4; i++) {
		int ny = y + y_dir[i];
		int nx = x + x_dir[i];
		if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
			if (map[ny][nx] == 0 && !air[ny][nx]) {
				airCheck(ny, nx);
			}
		}
	}
}
void meltPointCheck(int y, int x) {
	if (map[y][x] == 1) {
		int airCnt = 0;
		for (int i = 0; i < 4; i++) {
			int ny = y + y_dir[i];
			int nx = x + x_dir[i];
			if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
				if (air[ny][nx]) airCnt++;
			}
		}
		if (airCnt >= 2) meltPoint[y][x] = true;
	}
}
bool meltCheese() {
	bool continueMelt = false;
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			if (map[i][j]==1 && meltPoint[i][j]) {
				continueMelt = true;
				map[i][j] = 0;
			}
		}
	}
	return continueMelt;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];

	while (true) {
		memset(air, false, sizeof(air));
		airCheck(0,0);
		
		for (int i = 1; i < n; i++)
			for (int j = 1; j < m; j++)
				meltPointCheck(i, j);
		
		if(!meltCheese()) break;
		ans++;
	}
	cout << ans;
}