[BOJ] 백준 2638번 치즈 C++

문제

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

2638번: 치즈

풀이

골드5 치즈 문제를 풀고 이 문제를 접했다면 쉽게 풀 수 있었을 것이다.

이 치즈 문제는 골드5 치즈 문제와 다르게 치즈에서 각 치즈 격자의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것을 찾아내 녹여줘야하기 때문에 checkboard라는 2차원 배열을 새로 만들어 실내온도의 공기와 접촉한 변의 개수를 저장해주었다.

탐색을 하다가 치즈이면서, checkboard의 값이 0이면 1을 증가 시켜주고, 치즈이면서 checkboard의 값이 1이라면 원본 board의 값을 0으로 만들어 치즈를 녹여주었다. 추가로 방문처리를 해주었는데 그 이유는 board의 값이 0으로 바뀌면서 그 좌표에 대해서 탐색을 할 수도 있기 때문에 방문처리를 하여 이번 BFS에 녹게되어 0이된 board에 대해서는 탐색을 못하도록 막아주었다.

이렇게 설계한 BFS를 바탕으로 탐색을 하고 매 탐색마다 녹일 수 있는 상태인지 체크해주어(보드에 치즈가 남아 있는지) 확인하여 녹일 수 있으면 while문 안의 내용을 계속 진행하고 아니라면 시간을 출력해주고 프로그램을 종료해주었다.

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#define x first
#define y second

using namespace std;

int n, m;
int cnt = 0;
int board[101][101];
bool visited[101][101];
int checkBoard[101][101];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

bool canMelt()
{
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			if (board[i][j] == 1)
			{
				return true;
			}
		}
	}
	return false;
}

void reset()
{
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			visited[i][j] = false;
			checkBoard[i][j] = 0;
		}
	}
}

void bfs()
{
	queue<pair<int, int>> q;

	q.push({ 0,0 });
	visited[0][0] = true;

	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.x + dx[dir];
			int ny = cur.y + dy[dir];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
			{
				continue;
			}
			if (visited[nx][ny])
			{
				continue;
			}

			if (board[nx][ny] == 1 && checkBoard[nx][ny] == 0)
			{
				checkBoard[nx][ny]++;
				continue;
			}
			if (board[nx][ny] == 1 && checkBoard[nx][ny] == 1)
			{
				board[nx][ny] = 0;
				visited[nx][ny] = true;
				continue;
			}

			visited[nx][ny] = true;
			q.push({ nx, ny });
		}
	}
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m;

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

	while (true)
	{
		reset();
		cnt++;
		bfs();

		if (!canMelt())
		{
			cout << cnt;
			return 0;
		}
	}
}