[백준/BOJ] 백준 14502번 : 연구소

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

14502번: 연구소

완전 탐색(브루트 포스)을 이용해 문제를 해결했다.

빈칸 중 벽을 설치할 3곳을 조합으로 구해 벽을 설치하고 그때 바이러스가 퍼져 나간 뒤 안전 영역의 크기를 구한다. 모든 조합에 대해 이런 식으로 안전 영역의 크기를 구해서 그중 최대 안전영역의 크기를 찾는다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;

//(x,y)위치로부터 바이러스가 퍼져나가는 것
void virus(vector<vector<int>>& b, int x, int y)
{
	//기저 사례1:범위를 벗어날때
	if (x < 0 || y < 0 || x >= n || y >= m)
		return;
	//기저 사례2:벽을 만났을때
	if (b[x][y] == 1)
		return;
	//이곳을 감염시키고 인접한곳들을 다시 전파
	if (b[x][y] == 0)
	{
		b[x][y] = 2;
		virus(b, x - 1, y);
		virus(b, x + 1, y);
		virus(b, x, y - 1);
		virus(b, x, y + 1);
	}

	return;
}
//안전 영역을 체크
int check(vector<vector<int>> b)
{
	int num = 0;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (b[i][j] == 0)
			{
				num++;
			}

	return num;
}

int solve(vector<vector<int>> b, int num, int fromx, int fromy)
{
	vector<vector<int>> tempboard(b);
	int ret = 0;

	//벽 3개를 설치했을때
	if (num == 3)
	{
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
			{
				//이곳이 감염된곳이라면 인접한 곳들을 감염
				if (tempboard[i][j] == 2)
				{
					virus(tempboard, i - 1, j);
					virus(tempboard, i + 1, j);
					virus(tempboard, i, j - 1);
					virus(tempboard, i, j + 1);
				}
			}
		ret = check(tempboard);
		return ret;
	}

	//중복되지 않게 벽을 설치할 3곳을 찾는다
	for(int i=0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			//벽을 선택할때 중복된 선택을 방지하기 위한 조건
			if (((i > fromx) || (j > fromy)) && tempboard[i][j] == 0)
			{
				//이곳에 벽을 설치
				tempboard[i][j] = 1;
				ret = max(ret,solve(tempboard, num + 1, i, j));
				//벽 해제
				tempboard[i][j] = 0;
			}
		}
	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int temp;

	cin >> n;
	cin >> m;
	vector<vector<int>> board(n);

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

	cout << solve(board, 0, -1, -1);

	return 0;
}