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

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

2638번: 치즈

🔔 문제 : 

(5<= N,M<=100)인 N * M 크기의 모눈종이가 주어집니다.

 

0은 아무것도 안놓여진 상태, 1은 치즈가 놓여진 상태입니다.

 

치즈는 한 칸을 기준으로 하고, 양 4변에서 2변이상이 바깥 공기와 접촉 해 있다면, 1시간 후에 녹습니다.

 

또한 치즈 속의 공기가 밀폐된 곳은 바깥공기가 아니므로, 영향을 받지 않습니다.

 

치즈가 다 녹으려면 몇시간이 지내야 하는지 출력하는 문제입니다.

 

 

예를 들어 c로 그려져 있는 곳이 치즈가 녹는 곳입니다.

 

이때 모눈종이의 맨 가장자리에는 치즈가 놓이지 않습니다.

---

🔔 Kick Point :

 

겉 공기를 BFS()를 통해 따로 구해서, 전체 종이를 훑고 다닐 때,

 

치즈가 얼마나 바깥공기랑 접촉했는지 카운트 수만 올려주면 녹는 치즈를 쉽게 구할 수 있습니다.

 

 

저는 모눈종이가 n*m인 사실을 잊어버리고, bfs() continue 조건을 줄 때, n으로만 주는 실수를 하여 몇시간 동안 시간초과로 골머리를 앓았었습니다. 정말 조건을 잘 파악하고 섬세하게 코딩을 해야겠습니다.

---

🔔 Code :

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

// Variable
int n, m;
int paper[101][101];
int cntAttachAir[101][101];
bool isVisited[101][101];

int dy[4] = { -1, 1, 0 ,0 };
int dx[4] = { 0, 0, -1 ,1 };

// 바깥 공기 체크
void airCheck() {

	queue<pair<int, int>> q;
	q.push({ 0,0 });

	while (!q.empty()) {
		int _y = q.front().first;
		int _x = q.front().second;
		q.pop();

		if (isVisited[_y][_x]) continue;
		isVisited[_y][_x] = true;

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

			if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
			
			if (paper[ny][nx] == 1) {
				cntAttachAir[ny][nx]++;
			}
			else if (paper[ny][nx] == 0) {
				q.push({ ny, nx });
			}
		}
	}
}

// 치즈 녹이기
void melt() {

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (cntAttachAir[i][j] >= 2) paper[i][j] = 0;
		}
	}

}

// 치즈가 남아있는지 체크
bool check() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (paper[i][j] == 1) return true;
		}
	}
	return false;
}


int main() {

	// Input
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> paper[i][j];
		}
	}

	// Solve
	int hour(0);
	while (check()) {
		
		// 2차원 배열 초기화
		memset(isVisited, 0, sizeof(isVisited));
		memset(cntAttachAir, 0, sizeof(cntAttachAir));

		airCheck();
		melt(); // 치즈 녹이기
		hour++;
	}


	// Output
	cout << hour;

}

---