[백준/C++] 2638번 치즈
https://www.acmicpc.net/problem/2638
2638번: 치즈
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로
www.acmicpc.net
얼핏보면 까다로운 문제처럼 보일 수 있지만, 이 문제의 키포인트는 치즈의 외부 공기와 내부 공기를 잘 구분하면 된다!
그렇게 할 수만 있다면 외부 공기와 2면 이상 닿은, 즉 곧 녹을 치즈를 구하는 건 어렵지 않다.
그렇다면 어떻게 외부 공기와 내부 공기를 구분할까?
가장자리에는 치즈가 올 수 없다고 하였으므로, (0,0)에서 부터 bfs를 시작한다.
0,0에서 bfs를 통해 갈 수 있는 모든 곳은 외부 공기로, 굳이 표현해주지 않아도 되지만 2로 표현해주었다.
그리고 1을 만나면 (=치즈를 만나면) 외부 공기와 닿은 면의 수를 저장해주기 위한 배열을 하나 선언해준뒤, 해당 인덱스의 값을 1 증가 시켰다. 1을 만났을 땐, 큐에 넣는다던지 이런 작업없이 위처럼 배열의 인덱스만 1 증가 해주고 다음 for문을 실행하였기 때문에, 내부 공기(1 안에 있는 0)에 접근할 수 없게 된다!
그리고 한 점에 대한 bfs가 끝날 때 마다 externAir 배열이 2보다 큰 곳이 있다면(=녹는 치즈가 있다면) 0으로 없애주었고 true를 리턴하였다.
boolean 타입의 함수를 사용한 이유는, 더이상 녹을 수 있는 치즈가 없을 때 까지 반복해주기 위함이다!
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <cstring>
using namespace std;
int map[101][101];
int visited[101][101];
int externAir[101][101];
queue<pair<int,int>> q;
int n,m,ans;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
void bfs(int a, int b){
q.push({a,b});
map[a][b]=2;
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
if(visited[x][y]) continue;
visited[x][y] = true;
map[x][y]=2;
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
if(map[nx][ny]==1) externAir[nx][ny]++;
else if(!visited[nx][ny]){
q.push({nx,ny});
}
}
}
}
}
bool update(){
bool flag = false;
for(int i=0; i<n; i++) {
for (int j = 0; j < m; j++) {
if(externAir[i][j]>=2){
map[i][j]=0;
flag = true;
}
}
}
return flag;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> map[i][j];
}
}
while(1) {
memset(externAir,0,sizeof(externAir));
memset(visited,0,sizeof(visited));
bfs(0, 0);
if (update()) {
ans++;
}
else break;
}
cout << ans;
return 0;
}