BaekJoon 2638번: 치즈(C++)

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

2638번: 치즈

풀이법

1) while 반복을 통해, 빈 배열이 나올때 까지 반복하여 총 걸리는 시간을 확인한다.

2) 치즈의 상태가 담길 배열을 arr, arr2로 두개 선언하였다. 시간이 종료된 후에 한번에 바꾸는 것이 결과값에 영향을 끼치지 않기에 두 개를 선언하여 문제를 해결하였다.

3) visited는 현재 치즈가 있는 배열을 의미하며, visited2는 현재 외부공기를 의미한다.

4) (0,0)의 자리는 항상 빈 공기로 채워져 있으니, 외부 공기가 어디까지 미치는지를 bfs를 통해 visited2 배열에 담았다.

5) 이 후 현재 치즈가 있는 자리의 값들을 넣으며, 외부 공기와 접촉된 면이 2개 이상인 배열의 값을 0으로 바꾸어 주었다.

 

추가 예제 (예제 2번)

 

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

답: 3

#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define INF 987654321
using namespace std;

int n, m;
int arr[101][101];
int arr2[101][101];
int outSide[101][101];
bool visited[101][101];
bool visited2[101][101];
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
bool isEmpty()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (arr[i][j] == 1)
				return true;
		}
	}
	return false;
}
void divideOutSide(int a, int b) //외부 공기 나누기
{
	visited2[a][b] = true;
	queue<pair<int, int>> q;
	q.push({ a,b });
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nextX = nowX + vx[i];
			int nextY = nowY + vy[i];
			if (nextX < 0 || nextY < 0 || nextX >= n  || nextY >= m)
				continue;
			if (arr[nextX][nextY] == 0 && !visited2[nextX][nextY])
			{
				visited2[nextX][nextY] = true; //외부공기 배열에 담음
				q.push({ nextX,nextY });

			}
		}
	}
}
void bfs(int a, int b)
{
	visited[a][b] = true;
	queue<pair<int, int>> q;
	q.push({ a,b });
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second;
		q.pop();

		int cnt = 0;
		for (int j = 0; j < 4; j++)
		{
			int checkX = nowX + vx[j];
			int checkY = nowY + vy[j];
			if (checkX < 0 || checkY < 0 || checkX >= n || checkY >= m)
				continue;
			if (arr[checkX][checkY] == 0 && visited2[checkX][checkY]) //외부 공기와 접촉면 갯수 확인
				cnt++;
		}
		if (cnt >= 2)
			arr2[nowX][nowY] = 0;


		for (int i = 0; i < 4; i++)
		{
			int nextX = nowX + vx[i];
			int nextY = nowY + vy[i];
			if (nextX < 1 || nextY < 1 || nextX >= n - 1 || nextY >= m - 1)
				continue;
			if (arr[nextX][nextY] == 1 && !visited[nextX][nextY])
			{
				visited[nextX][nextY] = true;
				q.push({ nextX,nextY });
				
			}
		}
	}
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];
	int resAns = 0;
	while (isEmpty())
	{
		resAns++;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				visited[i][j] = false;
				visited2[i][j] = false;
				arr2[i][j] = arr[i][j];
			}
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				divideOutSide(0, 0);
			}
		}
		
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (arr[i][j] == 1&&!visited[i][j])
					bfs(i, j);
			}
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				arr[i][j] = arr2[i][j];
			}
		}

	}
	cout << resAns;
}