[C++] 백준 2638 - 치즈

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

2638번: 치즈

문제

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 1>

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

<그림 2>

<그림 3>

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

4

 

---

풀이

• 백준 2636 치즈(hhttps://www.acmicpc.net/problem/2636)와 유사한 문제로 치즈를 녹이기 위한 조건이 하나 추가된 문제이다.
• 바깥쪽에 있는 치즈 중 공기와 맞닿은 곳이 두면 이상일 경우 녹여줘야하기 때문에 2차원 배열에 존재하는 모든 공기를 2로 변경하여 치즈와 맞닿은 면을 체크하고, 치즈 주변에 있는 공기면의 수를 체크하여 녹여준다.
• 배열을 계속 탐색해야 하기 때문에 2로 변경했던 외부 공기를 다시 0으로 되돌린다.
• 배열에 치즈 존재하지 않을 때까지 BFS를 실행하여 녹는 시간을 증가시킨다.

 

전체 코드

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

using namespace std;

#define MAX 101
#define _X first
#define _Y second

int board[MAX][MAX];
bool visited[MAX][MAX];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

int N, M, hour;

queue<pair<int, int>> q;

// 2로 변경한 외부 공기를 다시 0으로 바꿔주는 함수
void ResetAir()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (board[i][j] == 2)
				board[i][j] = 0;
		}
	}
}

// 배열에 치즈가 존재하지 않을 경우 true, 존재할 경우 false 반환
bool HasAllMelted()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (board[i][j] != 0)
				return false;
		}
	}
	return true;

}

// 치즈 사방에 공기가 있을 경우 카운트 증가시킨 후, 두면이 공기라면 치즈를 녹임
void MeltCheese()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			int airCount = 0;
			if (board[i][j] != 1) continue;
			if (board[i + 1][j] == 2) airCount++;
			if (board[i - 1][j] == 2) airCount++;
			if (board[i][j + 1] == 2) airCount++;
			if (board[i][j - 1] == 2) airCount++;

			if (airCount >= 2)
			{
				board[i][j] = 0;
			}
		}
	}
}

void Bfs()
{
	q.push({ 0, 0 });
	visited[0][0] = true;
	hour++;

	while (!q.empty())
	{
		pair<int, int> cur = q.front();
		int x = cur._X;
		int y = cur._Y;
		q.pop();

		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) continue;
			if (board[nx][ny] != 0 || visited[nx][ny]) continue;
			// 공기를 2로 바꿔줌
			q.push({ nx, ny });
			board[nx][ny] = 2;
			visited[nx][ny] = true;
		}
	}
}


int main()
{
	cin.tie(0); cout.tie(0);

	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> board[i][j];
		}
	}

	while (true)
	{
		if (HasAllMelted())
		{
			cout << hour;
			break;
		}

		memset(visited, 0, sizeof(visited));
		Bfs();
		MeltCheese();
		ResetAir();
	}

	return 0;
}