14502번 - 연구소

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

14502번: 연구소

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int N, M;
int graph[8][8]; //사용자로부터 입력받을 배열
int map[8][8]; //벽을 설치하기 위한 배열
int spread[8][8]; //벽을 설치하고 바이러스를 확산시킬 배열
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

int ans = 0;
//배열 복사 함수
void mapCopy(int(*a)[8], int(*b)[8])
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			b[i][j] = a[i][j];

}
bool is_possible(int row, int col)
{
	if (row < 0 || row >= N || col < 0 || col >= M)
		return false;
	else
		return true;
}
void diffusion()
{
	mapCopy(map, spread);
	queue<pair<int, int>> q;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			//spread[i][j]가 바이러스라면
			if (spread[i][j] == 2)
				q.push(make_pair(i, j));
		}
	}
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
        //바이러스가 확산될 수 있는 경우 탐색
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (is_possible(nx, ny) && spread[nx][ny] == 0)
			{
				q.push(make_pair(nx, ny));
				spread[nx][ny] = 2; //바이러스 확산
			}
		}
	}
	int cnt = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (spread[i][j] == 0)
				cnt++;
	//ans와 cnt중 큰 값을 ans에 저장
	ans = max(ans, cnt);

}
void wall(int cnt)
{

	if (cnt == 3)
	{
		diffusion();
		return;
	}
	//벽 세우기
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (map[i][j] == 0)
			{
				map[i][j] = 1;
				wall(cnt + 1);
				map[i][j] = 0; //설치한 벽 다시 제거
			}
		}
	}
}
int main()
{
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			//안전 영역 0, 벽 1, 바이러스 2
			cin >> graph[i][j];
		}
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			//graph[i][j]에 벽이 설치 되어 있지 않으면
			if (graph[i][j] == 0)
			{
				mapCopy(graph, map);
				//map[i][j]에 벽 설치
				map[i][j] = 1;
				wall(1);
                //설치했던 벽 제거
				map[i][j] = 0;
			}
		}
	}
	cout << ans << '\n';
	return 0;
}