백준 14502 연구소

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

연구소에 벽이 있고 바이러스들이 존재할때 바이러스가 상하좌우로 퍼져 나갑니다. 이때 벽을 3개를 추가 시킬 수 있는데 바이러스가 퍼지지 않는 영역의 최대를 구하는 문제입니다. 연구소 크기가 최고 8*8이므로 그냥 벽이 없는 곳중에 3곳을 찾아 벽을 세우고 그 배열을 대상으로 bfs를 해서 안전영역을 구하면 되는 문제입니다.

 

재귀 함수를 통해 벽 3개를 추가 시켜주고 거기서 bfs를 통해 바이러스를 퍼트려 주면 됩니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <queue>
using namespace std;

int arr[8][8];
queue<pair<int, int>> q;
int N,M;
int nextx[4] = {1, 0, -1, 0};
int nexty[4] = {0, 1, 0, -1};
int maxnum;

void bfs(int (*arr)[8]) {
	
	int carr[8][8];
	int num = 0;
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++) {
			carr[i][j] = arr[i][j];
			
			if(arr[i][j] == 2)
				q.push(make_pair(i, j));
		}
		
		
	while(!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;
		
		for(int i = 0; i < 4; i++) {
			int x = xx + nextx[i];
			int y = yy + nexty[i];
			
			if(x < 0 || x > N-1 || y < 0 || y > M-1 || carr[x][y] != 0)
				continue;
			
			carr[x][y] = 2;
			q.push(make_pair(x, y));	
		}
		q.pop();
	}
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++)
			if(carr[i][j] == 0)
				num++;
	
	maxnum = max(maxnum, num);
	return;
}

void dfs(int x, int y, int n) { // 벽세울 위치 찾는 재귀함수 
	
	if(n == 3) {
		bfs(arr);
		return;
	}
	
	for(int i = x; i < N; i++)
		for(int j = y; j < M; j++)
			if(arr[i][j] == 0) {
				arr[i][j] = 1;
				dfs(x, y, n+1);
				arr[i][j] = 0;
			}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N >> M;
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++)
			cin >> arr[i][j];
			
	dfs(0, 0, 0);
	
	cout<<maxnum;
	return 0;
}