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

백준 14502

🌲 문제 요약

연구소의 지도가 주어졌을 때, 바이러스가 퍼질 수 없는 안전 영역 크기의 최댓값을 구하는 문제.

🌲 문제 풀이

세 개의 벽을 세울 수 있는 각각의 경우를 나누어, 안전 영역의 최대 크기를 구한다.
ret = max(ret, solve())의 연산을 통해 최댓값을 비교한다. 이때 solve 함수는 각 경우에 따라 dfs 함수를 부른 뒤, 해당 경우의 안전 영역 크기를 구하는 역할을 한다.
dfs 함수는 배열을 탐색하며 바이러스가 퍼진 위치의 정보를 visited에 저장한다.

🌲 주의

반복문을 통해 조합을 구현하는 과정에서, arr의 값을 변경했으니 함수 호출 이후 다시 원래대로 초기화해주어야 한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
int n, m, ret, arr[10][10], visited[10][10];
vector<pair<int, int>> virusList, wallList;

void dfs(int y, int x) {
	visited[y][x] = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
		if (!arr[ny][nx] && !visited[ny][nx]) {
			dfs(ny, nx);
		}
	}
	return;
}

int solve() {
	memset(visited, 0, sizeof(visited));
	for (pair<int, int> a : virusList) {
		dfs(a.first, a.second);
	}
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!arr[i][j] && !visited[i][j]) cnt++;
		}
	}
	return cnt;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 0) wallList.push_back({i, j});
			else if (arr[i][j] == 2) virusList.push_back({i, j});
		}
	}
	
	for (int i = 0; i < wallList.size(); i++) {
		for (int j = i + 1; j < wallList.size(); j++) {
			for (int k = j + 1; k < wallList.size(); k++) {
				arr[wallList[i].first][wallList[i].second] = 1;
				arr[wallList[j].first][wallList[j].second] = 1;
				arr[wallList[k].first][wallList[k].second] = 1;
				ret = max(ret, solve());
				arr[wallList[i].first][wallList[i].second] = 0;
				arr[wallList[j].first][wallList[j].second] = 0;
				arr[wallList[k].first][wallList[k].second] = 0;
			}
		}
	}
	cout << ret << '\n';
	
	return 0;
}