백준 2638 - 치즈(C++)

문제

N•M의 모눈종이 위에 아주 얇은 치즈가 다음과 같이 표시되어 있다.

회색 부분은 치즈를 나타내고 흰색 부분은 공기를 나타낸다.

 

이때 다음처럼 치즈 밖에 있는 공기를 외부 공기, 치즈 안에 있는 공기를 내부 공기라고 할 수 있다.

 

치즈는 외부 공기에 두 변 이상 만나게 되면 1시간 뒤에 사라진다.

 

그럼 모든 치즈가 다 녹게 되는데 몇 시간이 걸리게 될까?

 

이때 모눈정이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다.

 

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M이 주어진다. (5 ≤ N, M ≤ 100)

 

그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다.

 

예제 입력

8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

 

예제 출력

4

 

문제 해결

어디서 힌트를 얻을 수 있을까?

 

우선 문제는 외부 공기와 내부 공기로 공기를 구분하는 것을 알 수 있다. 그리고 가장자리의 부분에는 치즈가 없는 것으로 가정한다.

 

또한, 치즈는 외부 공기와 두 변 이상 만났을 때 사라지는 것을 통해 공기는 상, 하, 좌, 우로 움직인다는 것을 알 수 있다.

 

이를 통해 (0, 0) 좌표에서 시작하여 공기가 상, 하, 좌, 우로 움직이면서 각 좌표에다가 1을 더해서 나가고 한 번 방문한 외부 공기 좌표에는 두 번 다시 가지 않는다면 모든 외부 공기의 좌표 값에는 1이라는 값이 들어가게 될 것이다. 

 

또한, 치즈를 만났을 때 +1을 하고 치즈 좌표값에서 부터 상, 하, 좌, 우 좌표값을 넣지 않는다면 치즈는 외부 공기와 만나는 면 만큼 +1하게 될 것이다.

 

그리고 내부 공기는 치즈로 인해서 진로가 막혀있기 때문에 +1이 될 수 없어 0이 될 것이다.

 

이를 그림으로 나타내면 다음과 같다.

 

 

즉, 각 좌표를 기준으로 상, 하, 좌, 우로 움직이기 때문에 다음과 같이 해당 치즈에는 몇 개의 공기와 만났는지 알 수 있다. 그리고 이는 BFS로 해결할 수 있다.

 

그럼 해당 좌표의 값이 2 이상인 것을 지우는 것을 반복하면 최종적으로 얼마의 시간이 지난지 알 수 있다.

 

 

코드

#include <iostream>
#include <queue>
#include <cstring>
#include <utility>

typedef std::pair<int, int> P;

int board[101][101];
int melted[101][101];
int cache[101][101];
int N, M;
int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};

void touchOutAir(void)
{
	std::queue<P > pq;

	pq.push(P(0, 0));
	cache[0][0] = 1;
	while (!pq.empty())
	{
		int cy = pq.front().first;
		int cx = pq.front().second;
		pq.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = cy + dy[i];
			int nx = cx + dx[i];
			if (ny >= 0 && ny < N && nx >= 0 && nx < M && !cache[ny][nx])
			{
				if (board[ny][nx] == 1)
					melted[ny][nx] += 1;
				else
				{
					pq.push(P(ny, nx));
					cache[ny][nx] = 1;
				}
			}
		}
	}
}

bool checkMelted(void)
{
	bool ret = false;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (melted[i][j] >= 2)
			{
				board[i][j] = 0;
				ret = true;
			}
		}
	}
	return ret;
}

int solve(void)
{
	int ret = 0;

	bool melt = false;
	while (1)
	{
		std::memset(melted, 0, sizeof(melted));
		std::memset(cache, 0, sizeof(cache));

		touchOutAir();
		bool melt = checkMelted();
		if (melt)
			ret++;
		else
			break ;
	}
	return ret;
}

int main(void)
{
	std::cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
			std::cin >> board[i][j];
	}
	std::cout << solve() << std::endl;
	return 0;
}

 

 

문제 출처

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

2638번: 치즈