[백준][14502][c++] 연구소

연구소 문제 링크

[풀이]
N과 M의 최대 값이 8이고, 벽은 3개라고 해서 조합,브루트 포스, BFS를 통해 최대 안전 지대 개수를 구할 수 있었다. 하지만 벽을 세운 후에 다시 벽을 허물어야 하는 작업도 있고, 안전지대 개수를 더해야 하는 것도 있기 때문에 시간이 길어질 것이 예상되어서 줄이기 위한 작업을 했다.

• 벽 3개를 가능한 곳에 다 세워본다 (조합)
• BFS를 통해 바이러스를 인접한 빈칸에다가 퍼트린다 (BFS)
• 안전지대를 계산해서 최대 안전지대를 구한다

[코드]

#include <iostream>
#include <vector>
#include <queue>
#define N_MAX 9

using namespace std;

int N, M;
int num_ones = 0;
int max_value = -1;
int map[N_MAX][N_MAX];
vector<pair<int, int>> zeros;
vector<pair<int, int>> zero_candidate;

int dir_y[] = { 1,-1,0,0 };
int dir_x[] = { 0,0,1,-1 };

void make_wall(vector<pair<int, int>>& candidate) {
	for (int i = 0; i < candidate.size(); i++) {
		pair<int, int> wall = candidate[i];
		map[wall.first][wall.second] = 1;
	}
}


void demake_wall(vector<pair<int, int>>& candidate) {
	for (int i = 0; i < candidate.size(); i++) {
		pair<int, int> wall = candidate[i];
		map[wall.first][wall.second] = 0;
	}
}

int spread_virus() {
	bool visited[N_MAX][N_MAX] = {false, };
	int num_virus = 0; //바이러스 개수 세기

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			//방문 안 했고 바이러스 있는 곳을 시작점으로 함
			if (visited[y][x]) continue;
			if (map[y][x] != 2) continue;

			queue<pair<int, int>> q;
			q.push(make_pair(y, x));
			visited[y][x] = true;
			num_virus++;
			while (!q.empty()) {
				pair<int, int> cur = q.front();
				q.pop();

				for (int dir = 0; dir < 4; dir++) {
					int new_y = cur.first + dir_y[dir];
					int new_x = cur.second + dir_x[dir];

					if (new_y < 0 || new_y >= N || new_x < 0 || new_x >= M) continue;
					if (visited[new_y][new_x]) continue;
					if (map[new_y][new_x] == 1) continue;

					num_virus++;
					visited[new_y][new_x] = true;
					q.push(make_pair(new_y, new_x));
				}
			}

		}
	}

	//전체 map 사이즈에서 벽이랑 바이러스가 없는 것이 안전지대!
	return N * M - num_ones - 3 - num_virus;
}

void combination(int idx, int depth, vector<pair<int, int>>& candidate) {
	if (depth == 3) {
		make_wall(candidate);    //벽 세우기
		int ans = spread_virus(); //바이러스 퍼트리기
		if (ans > max_value) max_value = ans;
		demake_wall(candidate);  //세운 벽 허물기
	}
	else {
		for (int i = idx; i < zeros.size(); i++) {
			candidate.push_back(zeros[i]);
			combination(i + 1, depth + 1, candidate);
			candidate.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];
			if (map[y][x] == 0) {
				//빈칸에 벽을 세우는 것이기에 빈칸 모으기
				zeros.push_back(make_pair(y, x));
			}
			else if (map[y][x] == 1) {
				//이미 세워진 벽 개수 세기
				num_ones++;
			}
		}
	}
	//빈칸 중에 벽 3개 세워야 함
	combination(0, 0, zero_candidate);
	cout << max_value << "\n";
}

[총평]
벽을 세우고 허물고 하는 것이랑 안전지대를 계산하는 것을 조금만 생각하면 쉽게 구할 수 있는 문제 인 것 같다.