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

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력하는 문제이다.(전형적인 BFS문제)

 

문제 해결 방법

1. 노출된 치즈의 위치 판별하기

2. 노출된  치즈를 녹이기

3. 위 과정을 치즈가 다 녹을 때까지 반복

 

노출된 치즈의 위치를 판별하기만 하면 풀리는 문제이다.

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

문제에 보면 가장자리에는 X표시가 되어있다는 사실을 알 수 있다. 가장자리에는 치즈를 놓지 않는다는 말이다.

즉 가장자리의 어떠한 부분에서 시작해서 치즈를 만날 때까지 너비우선탐색 해주면 치즈의 위치를 찾을 수 있다는 말이다.

무한 루프 방지를 위해 visited를 통해 방문했던 장소를 저장하고 만약 그곳이 치즈였다면 1을 0으로 수정.

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

 

#include <iostream>
#include <queue>

using namespace std;

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

int BFS();

int a=0;
int b=0;

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

int BFS()
{
	int visited[101][101]={0};
	
	int count=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]]==0&&num1+row[i]>-1&&num1+row[i]<a&&num2+col[i]>-1&&num2+col[i]<b)
			{
				visited[num1+row[i]][num2+col[i]]=1;

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