작은시작

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

코드 설명

map과 copy_map으로 기존 맵과 다른 맵 하나를 만들어준다. 

map에 완전탐색을 통해 벽을 3개 만든다. 그때마다 copy_map으로 복사해주고 바이러스를 퍼뜨려본다.

그때마다 안전구역을 찾아주고 최대일 때를 저장해둔다.

다시 map으로 돌아와 다음 벽3개를 세워본다.

map에 벽세우기 -> copy_map 복사 -> copy_map 바이러스 감염 -> 안전구역 최대 개수 저장 -> 처음 map으로 돌아가기 

코드

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,1,-1 };
int map[10][10];
int copy_map[10][10];
bool visited[10][10];
int N, M;
int answer;
queue<pair<int, int>> q;
int result;
void bfs() {

	
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (!visited[ny][nx] && copy_map[ny][nx]!=1) {
				q.push({ ny,nx });
				visited[ny][nx] = true;
				copy_map[ny][nx] = 2; //감염 
			}
		}

	}


}

void dfs(int level,int y, int x) {

	if (level == 3) {
		memcpy(copy_map, map, sizeof(map));
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if (copy_map[y][x] == 2) {
					q.push({ y,x });
					
					visited[y][x] = true;
				}

			}
		}
		bfs();
		result = 0;
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if (copy_map[y][x] == 0) {
					result++;
					
				}

			}
		}
		answer = max(answer, result);
		memset(visited, false, sizeof(visited));
		

		return;

	}


	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (map[y][x]==0) {
				map[y][x] = 1; //벽세우기
				dfs(level + 1, y, x);
				map[y][x] = 0;
			}
		}
	}

}
int main() {
	cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];
		}
	}

	memcpy(copy_map, map, sizeof(map));

	//벽 3개 전부 세워보기
	dfs(0,0, 0);


	cout << answer;

	return 0;
}