[백준] 2638번 치즈 C++

🥇 Gold 3 치즈 문제풀이

문제설명

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

<그림 1>

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

<그림 2>

<그림 3>

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

---

C++ 풀이

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

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

// 공기와 한 면 이상 접촉한 칸(치즈)은 한 시간 뒤 녹는다.
// 치즈에 난 구멍은 초기에는 공기로 간주되지 않지만,
// 구멍이 치즈 외부와 접촉되는 순간 공기로 간주된다.

vector<pair<int, int> > checkAir(int n, int m, int hour)
{
	bool check[101][101] = {false, };
	bool visited[101][101] = {false, };
	queue<pair<int, int> > Q;
	vector<pair<int, int> > res;
	Q.push(make_pair(0, 0));
	visited[0][0] = true;
	while (!Q.empty())
	{
		auto cur = Q.front();
		Q.pop();
		board[cur.first][cur.second] = hour;
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
				continue;
			if (board[nx][ny] == -1)
			{
				if (check[nx][ny])
					res.push_back(make_pair(nx, ny));
				else
					check[nx][ny] = true;
				continue;
			}
			if (visited[nx][ny])
				continue;
			Q.push(make_pair(nx, ny));
			visited[nx][ny] = true;
		}
	}
	return (res);
}

int main()
{
	int n, m, hour, last, survives;
	cin >> n >> m;
	
	// 치즈 위치 입력
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> board[i][j];
			if (board[i][j] == 1)
				board[i][j] = -1;
		}
	}
	hour = 1;
	last = 0;
	survives = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (board[i][j] == -1)
				survives++;
		}
	}
	while (1)
	{
		last = survives;
		auto cheese = checkAir(n, m, hour);
		for (int i = 0; i < cheese.size(); i++)
		{
			board[cheese[i].first][cheese[i].second] = hour;
		}
		survives = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (board[i][j] == -1)
					survives++;
			}
		}
		if (survives == 0)
		{
			cout << hour << '\n';
			break;
		}
		hour++;
	}
}

---

추가 설명

2636번 치즈 문제를 풀었다면 단 몇줄의 코드 수정으로 통과를 받을 수 있는 문제다. 2636번과 동일하게 공기에 닿은 영역은 한 시간 뒤 사라지는 부분이 같지만, 2636번은 한 면이라도 닿으면 사라지지만, 이 문제에서는 두 면 이상이 공기에 닿아야 치즈가 사라지게 된다.
따라서 2636번의 기본 틀인 BFS는 동일하게 유지하되, 공기에 닿는 횟수를 세는 부분을 추가하였다.

함수 checkAir 에서 bool check 배열이 존재하는데, 처음에는 다 false(0)으로 초기화 된 상태지만, 한 번 공기가 닿으면 true(1)로 변하게 된다. 이후 true인 상태에서 한 번 더 닿으면 반환하는 vector에 좌표가 들어가게 된다.