[백준] 2638번 : 치즈 [C/C++]

#문제

2638번: 치즈

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

2638번: 치즈

 

---

#접근방법

 

치즈가 두 변 이상이 공기와 접촉할 때 녹는다. 단, 바깥이 치즈로 둘러쌓여있는 공기일 경우에는 접촉하더라도 카운팅이 되지 않는다. 치즈가 녹고 안쪽 공기가 외부 공기와 접촉할 경우에 안쪽 공기를 외부 공기로 변환시켜주면서 치즈가 녹는 경우를 구하면 된다.

반응형

---

#풀이

#include <stdio.h>
#include <queue>
using namespace std;

int arr[105][105];
int xx[4]={0,0,-1,1};
int yy[4]={1,-1,0,0};
int n,m;
int ans;
queue<pair<int,int> > q;

void dfs(int x,int y){
	if(arr[x][y]==0)
		arr[x][y]=-1;
	else return;
	
	for(int i=0;i<4;i++){
		int X = x+xx[i];
		int Y = y+yy[i];
		
		if(X>=1 && X<=n && Y>=1 && Y<=m)
			dfs(X,Y);
	}
	
	return;
}

int main(){
	scanf("%d %d",&n,&m);
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&arr[i][j]);
	
	dfs(1,1);
	while(true){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(arr[i][j]==1){	
					int cnt = 0;
					for(int k=0;k<4;k++){
						int X = i+xx[k];
						int Y = j+yy[k];

						if(arr[X][Y]==-1) cnt++;
					}

					if(cnt>=2)
						q.push(make_pair(i,j));
				}
		
		if(q.empty()) break;
		
		while(!q.empty()){
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			
			arr[x][y] = -1;
			
			for(int i=0;i<4;i++){
				int X = x+xx[i];
				int Y = y+yy[i];
				
				if(arr[X][Y]==0)
					dfs(X,Y);
			}
		}
		
		ans++;
	}
	
	printf("%d",ans);
	
	return 0;
}

 

n,m을 입력받고 arr배열에 치즈와 공기를 저장시켜주었다.

 

문제 조건에서 가장자리는 치즈가 없다고 가정을 하였다. 따라서 arr[1][1]은 무조건 외부공기이므로 dfs(1,1)을 실행하여서 외부 공기를 -1로 치환시켜주었다.

 

그러면 arr배열에는 -1(외부공기), 1(치즈), 0(내부공기)로 총 3가지 숫자가 존재할 것이다. (0은 없는 경우도 있다.)

 

이중 반복문으로 arr배열을 탐색해준다. arr[i][j]==1이면서 상,하,좌,우 중 -1이 2개 이상일 때, queue에 (i,j)좌표를 저장시켜주었다.

 

queue에 들어있는 좌표들은 녹는 치즈들의 좌표이므로 -1로 치환해주고 치즈가 녹으면서 상,하,좌,우에 0이 있으면 dfs에 0이 들어있는 좌표를 넣어주어서 인접해있는 0 (내부공기)들을 -1 (외부공기)로 치환시켜준다.

 

그리고 ans를 1증가시켜준다.

 

이 과정을 치즈가 다 녹을 때까지 반복해주고 ans를 출력하면 정답이다.

---

#성능

---

#정리

치즈가 녹고 외부공기와 내부공기가 접촉할 때 dfs로 내부공기를 외부공기로 치환시켜 주는 것,

 

이를 구현할 수 있는 구현력을 갖추고 있으면 풀 수 있는 문제였다.