14502번 연구소

문제링크

코드 설명

벽 3개를 완전탐색(DFS)를 이용하여 선정한후 vector에 넣는다.
이후 BFS를 통해 바이러스를 퍼져나가게한후 0의 갯수를 센다

가능한 방법을 전부 탐색하여 0의 갯수가 최대가 될때까지 반복한다.(완전탐색+BFS)

코드

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

int N, M;
int map[10][10];

queue<pair<int, int>>q;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int temp_map[10][10];
vector<pair<int, int>> wall_index;
int cnt;
int answer;
void bfs() {
	int cnt = 0;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (map[y][x] == 2) {
				q.push({ y,x });
			}
		}
	}

	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 (temp_map[ny][nx] == 1) continue;
			if (temp_map[ny][nx] == 0) {
				temp_map[ny][nx] = 2;
				q.push({ ny,nx });
				
			}

		}


	}
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (temp_map[y][x] == 0) cnt++;
		}
	}
	if (answer < cnt) answer = cnt;

	


}
void run(int level,int now) {
	
	if (level == 3) {
		memcpy(temp_map, map, sizeof(map));
		for (int i = 0; i < 3; i++) {
		temp_map[wall_index[i].first][wall_index[i].second] = 1;
		
		}
		bfs();
		
		return;
	}


	for (int i = now; i < wall.size(); i++) {
		
		int y = wall[i].first;
		int x = wall[i].second;
		wall_index.push_back({ y,x });
		run(level + 1, i + 1);
		wall_index.pop_back();
	}

}

int main() {
	cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];
		
		}
	}
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (map[y][x] == 0) {
				wall.push_back({ y,x });
			}
		}
	}
	
	memcpy(temp_map, map, sizeof(map));
	run(0,0);

	cout << answer;
	return 0;
}