❓문제 설명

문제 : 백준 2638 치즈

난이도 : 골드 3

문제 정보

• N은 세로, M은 가로 입니다.
• 치즈 외부 공기와 치즈의 2변 이상이 접촉하면 한 시간 뒤에 녹습니다.
• 회색으로 칠해진 부분은 치즈를 나타내고 C가 그려진 부분은 한 시간 후에 사라지는 치즈를 나타냅니다.
• <그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않은 것으로 가정합니다.
• 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정합니다. 즉, 0,0 과 같은 모서리에는 치즈가 존재하지 않습니다.

---

• <그림 1>에서 C 하나를 살펴보면 외부 공기와 2변이 접촉했기 때문에 C가 맞습니다.

• C가 아닌 부분을 보면 1변만 외부 공기와 접촉했기 때문에 C가 아닙니다.

• <그림 2>에 제가 노란색 V를 칠한 부분은 치즈 내부이므로 외부 공기로 간주하지 않습니다.

• 그러므로 제가 가리키고 있는 치즈 부분은 외부 공기와 1변만 접촉하므로 C가 아닙니다.

• <그림 2>에서 C로 칠해진 치즈들이 녹은 뒤에는 치즈 내부였던 부분들이 외부 공기와 섞이면서 외부 공기로 간주됩니다.

• 이제 치즈가 모두 녹는 시간을 구하면 됩니다.

🎯문제 해결 방법

이 문제는 그래프 문제이면서 문제에서 주어진 순서대로 차례차례 구현해나가는 구현 문제이기도 합니다.

구현 문제를 풀 때는 어떤 것들이 필요할지 생각해보는게 좋습니다.

1. 외부 공기들을 먼저 체크해줍니다.

2. 치즈가 다 녹을 때 까지 반복하면서 치즈가 다 녹았는지 확인하는 함수

3. 맨 처음 외부 공기들로 인해 C로 칠해질 치즈 부분을 찾습니다. 가장자리 (0,0)에는 치즈가 존재하지 않고 외부 공기이므로 (0,0)를 시작으로 BFS 해주도록 합니다.

4. C로 칠할 치즈들을 찾고 녹여주는 작업을 합니다.

5. 치즈가 녹으면서 치즈 내부였던 공기가 외부 공기와 섞이는 부분이 있는지 확인합니다.

6. (2) ~ (5) 과정을 반복합니다.

int n,m; // 세로, 가로
int a[104][104]; // 모눈종이 정보
bool vst[104][104]; // 외부 공기인지 표시
int dx[4] = {1,-1,0,0}; 
int dy[4] = {0,0,1,-1};
vector<pair<pair<int,int>, bool>> v; // { {y,x}, 녹았는지 }
vector<pair<int,int>> cheese; // 다음으로 녹을 치즈들을 담음
queue<pair<int,int>> qq; // 치즈가 녹은 자리들을 담습니다.

1번 과정

void air() { 
	queue<pair<int,int>> q;
	q.push({0,0}); // 가장 자리부터 시작합니다.
	vst[0][0] = 1;
	while(!q.empty()){
		auto cur = q.front(); q.pop();
		for(int dir=0; dir<4; dir++){
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
			if(!vst[ny][nx]){
				vst[ny][nx] =1;
				q.push({ny,nx});
			}
			
		}
	}
}

2번 과정

bool chk() {
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(a[i][j] == 1) return false;
		}
	}
	return true;
}

• 간단합니다. 치즈는 1로 표시되고 치즈가 남아있는지만 확인하는 함수입니다.

3번 과정

void find() {
	cheese.clear();
	for(int i=0; i<v.size(); i++){
		if(v[i].second) continue; // 이미 녹은 치즈는 지나갑니다.
		int y = v[i].first.first;
		int x = v[i].first.second;
		int cnt = 0;
		for(int dir=0; dir<4; dir++){
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if(a[ny][nx] == 0 && vst[ny][nx]) cnt++; // 치즈가 아니면서 외부 공기를 만나면 cnt를 하나 더해줍니다.
		}
		if(cnt >= 2){
			cheese.push_back({y,x});
			v[i].second = true; // 녹을 치즈로 바꿔줍니다.
		}
	}
}

4번 과정

void melt() {
	for(int i=0; i<cheese.size(); i++){
		int y = cheese[i].first;
		int x = cheese[i].second;
		a[y][x] = 0; // 치즈가 아닌 것으로 표시
		qq.push({y,x}); // 녹은 치즈의 위치를 담습니다.
	}
}

5번 과정

void add() {
	while(!qq.empty()){
		auto cur = qq.front(); qq.pop();
		vst[cur.Y][cur.X] = 1;
		for(int dir=0; dir<4; dir++){
			int ny = cur.Y + dy[dir];
			int nx = cur.X + dx[dir];
			if(!vst[ny][nx]){ // 치즈가 녹은 자리 근처에서 외부 공기가 아닌 부분을 찾으면
				vst[ny][nx] = 1;
				qq.push({ny,nx});
			}
		}
	}
}

마지막으로 이 과정들을 거치고도 치즈가 다 녹지 않았다면 1시간을 더해줍니다.

💻전체 코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define Y first
#define X second
using namespace std;
int n,m;
int a[104][104];
bool vst[104][104];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
vector<pair<pair<int,int>, bool>> v;
vector<pair<int,int>> cheese;
queue<pair<int,int>> qq;

void air() { 
	queue<pair<int,int>> q;
	q.push({0,0});
	vst[0][0] = 1;
	while(!q.empty()){
		auto cur = q.front(); q.pop();
		for(int dir=0; dir<4; dir++){
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
			if(!vst[ny][nx]){
				vst[ny][nx] =1;
				q.push({ny,nx});
			}
			
		}
	}
}

void find() {
	cheese.clear();
	for(int i=0; i<v.size(); i++){
		if(v[i].second) continue;
		int y = v[i].first.first;
		int x = v[i].first.second;
		int cnt = 0;
		for(int dir=0; dir<4; dir++){
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if(a[ny][nx] == 0 && vst[ny][nx]) cnt++;
		}
		if(cnt >= 2){
			cheese.push_back({y,x});
			v[i].second = true;
		}
	}
}

void melt() {
	for(int i=0; i<cheese.size(); i++){
		int y = cheese[i].first;
		int x = cheese[i].second;
		a[y][x] = 0;
		qq.push({y,x});
	}
}

void add() {
	while(!qq.empty()){
		auto cur = qq.front(); qq.pop();
		vst[cur.Y][cur.X] = 1;
		for(int dir=0; dir<4; dir++){
			int ny = cur.Y + dy[dir];
			int nx = cur.X + dx[dir];
			if(!vst[ny][nx]){
				vst[ny][nx] = 1;
				qq.push({ny,nx});
			}
		}
	}
}

bool chk() {
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(a[i][j] == 1) return false;
		}
	}
	return true;
}

int main(void){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cin >> a[i][j];
			if(a[i][j] == 1){
				v.push_back({{i,j}, false});
				vst[i][j] = 1;
			}
		}
	}
	int ret = 0;
	air();
	while(1){
		if(chk()) break;
		find();
		melt();
		add();
		ret++;
	}
	cout << ret;
	return 0;
}