BOJ 14502 : 연구소

[정답코드]

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

const int MAX = 9;
//int map[MAX][MAX];
int N, M;
vector<pair<int, int>> virus; //y,x
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};
int ans=-1;

int count_safe(vector<vector<int>>& v) {
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (v[i][j] == 0) cnt++;
		}
	}
	return cnt;
}

void dfs(vector<vector<int>>&v) {
	queue<pair<int, int>> q;
	for (int i = 0; i < virus.size(); i++) {
		q.push({ virus[i].first,virus[i].second });
	}
	while (!q.empty()) {
		int curY = q.front().first;
		int curX = q.front().second;
		q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nextY = curY + dy[dir];
			int nextX = curX + dx[dir];
			if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M)continue;
			if (v[nextY][nextX] == 0) {
				q.push({ nextY,nextX });
				v[nextY][nextX] = 2;
			}
		}
	}
	int ret = 0;
	ret= count_safe(v);
	ans = max(ans, ret);
}

//벽 위치를 정하는 함수
void wall_bfs(vector<vector<int>>v, int y, int x, int cnt) {
	//해당 위치에 벽을 세움
	v[y][x] = 1;
	//cout << y << x <<cnt<<"\n";
	if (cnt == 0) {
		dfs(v);
		return;
	}
	for (int i = y; i < v.size(); i++) {
		for (int j = 0; j < v[y].size(); j++) {
			if (v[i][j] == 0) {
				wall_bfs(v, i, j, cnt-1);
			}
		}
	}
}

int main() {
	//N=세로,y M=가로,x
	cin >> N >> M;
	//이차원 벡터 선언
	vector<vector<int>> map(N,vector<int>(M));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int temp;
			cin >> temp;
			map[i][j] = temp;
			if (temp == 2) {
				virus.push_back({ i,j });
			}
		}
	}
	   
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) {
				wall_bfs(map, i, j, 2);
			}
		}
	}

	//map 체크
	/*
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cout << map[i][j];
		}
		cout << "\n";
	}
	*/
	
	cout << ans << "\n";


	return 0;
}