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

 

주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력하는 문제이다.

 

문제 해결 방법

1. 노출된 치즈의 위치를 찾는다

2. 노출된 치즈를 녹인다.

3. 위 과정을 반복한다.

 

그렇다면 노출된 치즈의 위치를 어떻게 판별할까??

노출된 치즈는 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것으로 정의되어있다.

즉 치즈가 2번 방문 되어야한다는 말이다.

 

보통은 visited가 0이면 방문을 하고  vistied를 1로 바꾸는데 이 문제에서 나는 vistied가 2 미만이면 방문을 하도록 설정하였다.

공기를 지나가게 되면 vistied를 2로 바꾸고 치즈를 만나면 visited++를 해주어서 노출된 치즈의 위치를 찾았다.

if(arr[num1+row[i]][num2+col[i]]==0)
{
	visited[num1+row[i]][num2+col[i]]=2;
	Q.push(make_pair(num1+row[i],num2+col[i]));
}
else
{
	visited[num1+row[i]][num2+col[i]]++;
	if(visited[num1+row[i]][num2+col[i]]==2)
	{
		arr[num1+row[i]][num2+col[i]]=0;
		count++;			
	}
}

위 과정을 치즈가 다 녹을 때까지 반복해주면 끝난다.

 

#include <iostream>
#include <queue>

using namespace std;

int arr[101][101];
queue <pair<int,int> > Q;
int row[4]={0,0,-1,1};
int col[4]={-1,1,0,0};
int N=0;
int M=0;
int count=0;

void BFS();

int main(void)
{
	
	int sum=0;
	
	cin>>N>>M;
	
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<M; j++)
		{
			cin>>arr[i][j];
			if(arr[i][j]==1)
			{
				sum++;
			}
		}
	}
	
	int page=0;
	
	while(true)
	{
		BFS();
		page++;
		if(count==sum)
		{
			cout<<page;
			break;
		}
	}
	
	return 0;
}

void BFS()
{
	int visited[101][101]={0};
	Q.push(make_pair(0,0));
	
	while(!Q.empty())
	{
		int num1=Q.front().first;
		int num2=Q.front().second;
		Q.pop(); 
		
		for(int i=0; i<4; i++)
		{
			if(visited[num1+row[i]][num2+col[i]]<2&&num1+row[i]>-1&&num1+row[i]<N&&num2+col[i]>-1&&num2+col[i]<M)
			{
				
				if(arr[num1+row[i]][num2+col[i]]==0)
				{
					visited[num1+row[i]][num2+col[i]]=2;
					Q.push(make_pair(num1+row[i],num2+col[i]));
				}
				else
				{
					visited[num1+row[i]][num2+col[i]]++;
					if(visited[num1+row[i]][num2+col[i]]==2)
					{
						arr[num1+row[i]][num2+col[i]]=0;
						count++;	
					}
				}
			}
		}
	}
}