[백준] 2636번 치즈 C++

🥇 Gold 4 치즈 문제풀이

문제설명

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

<그림 1> 원래 치즈 모양

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 2> 한 시간 후의 치즈 모양

<그림 3> 두 시간 후의 치즈 모양

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 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 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;
            // 공기가 치즈랑 닿은 순간
            // 해당 치즈 칸은 1시간 뒤에 사라짐
			if (board[nx][ny] == -1)
			{
				res.push_back(make_pair(nx, ny));
				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';
			cout << last << '\n';
			break;
		}
		hour++;
	}
}

---

추가 설명

치즈 영역을 시간이 흐름에 따라 없애 나가는 재밌는 문제.
기본적으로 BFS를 사용해야 하는 문제다.
'공기'의 영역을 매 시간마다 체크를 하고, '공기'에 닿는 '치즈'를 한 시간 뒤에 사라지게 해야 한다.
공기의 영역 체크를 checkAir 함수에서 이루어지게 했는데, checkAir 함수는 BFS로 공기 영역을 현재 시간으로 지속적으로 바꾸고, 공기 영역에서 상하좌우로 닿은 치즈 영역의 좌표를 vector에 담아 반환한다.
이렇게 반환된 치즈 좌표를 전부 한 시간 뒤에 공기 영역으로 바꿔주는 과정을 반복한다.

한 가지 풀이 포인트는, 시간이 0부터 1, 2, 3... 이렇게 흐르기 때문에 치즈 영역을 -1로 두고 풀었던 점이다. 이렇게 하면 양의 정수로 흐르는 시간에 상관없이 치즈 영역을 계속 일정하게 표시 가능하다.