BaekJoon 14502번: 연구소

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

14502번: 연구소

풀이법

1) 바이러스가 퍼지는 것을 방지하기 위해 벽을 정확히 3개 세울 수 있다는 것에 유의하며 문제를 풀어야 한다.

2) 8x8 배열이므로 완전 탐색을 진행하였으며 벽을 세우는 것은 dfs 알고리즘을 활용하였다.

3) 벽이 3개 세워진 이후에는 bfs 알고리즘을 활용하여 안전 지대의 크기를 확인하여 문제를 해결하였다.

(기존의 입력 값의 배열을 그대로 사용 시에 문제를 해결할 수 없다. 꼭 같은 크기의 배열을 만들고 복사하여 복사된 배열에서 값이 계산될 수 있도록 해야 문제 없이 해결 가능하다는 것을 유의하자)

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

int n, m;
int arr[8][8];
int temp[8][8];
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
bool visited[8][8][3];
int result = 0;
void bfs()
{
	int c_arr[8][8];
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			c_arr[i][j] = temp[i][j];
	}
	queue<pair<int, int>> q;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			if (c_arr[i][j] == 2)
				q.push({ i,j });
	}
	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 (c_arr[nextX][nextY] == 0)
			{
				c_arr[nextX][nextY] = 2;
				q.push({ nextX,nextY });
			}
			
		}
	}
	int theResult = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (c_arr[i][j] == 0)
				theResult++;
		}
	}
	result = max(result, theResult);
}
void makeWall(int cnt)
{
	if (cnt == 3)
	{
		bfs();
		return;
	}
	for(int i=0; i<n;i++)
		for(int j=0;j<m;j++)
			if (temp[i][j] == 0)
			{
				temp[i][j] = 1;
				makeWall(cnt + 1);
				temp[i][j] = 0;
			}
}
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];
		}
	}
	
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (arr[i][j] == 0)
			{
				for (int k = 0; k < n; k++)
				{
					for (int l = 0; l < m; l++)
					{
						temp[k][l] = arr[k][l];
					}
				}
				temp[i][j] = 1;
				makeWall(1);
				temp[i][j] = 0;
			}
		}
	}
	cout << result;
}