c++ 14502번 연구소 (백준)

#include <bits/stdc++.h>
#define Q q.front()
using namespace std;

int V[4] = {-1, 0, 1, 0};
int H[4] = {0, 1, 0, -1};
int n, m, zero = -3; //벽 3개를 무조건 설치하므로 -3으로 시작합니다.
int Max = 0;
int Map[8][8] = {};
vector<pair<int, int> > two;

void bfs(void) { //bfs
	queue<pair<int, int> > q; //큐
	int cnt = zero; //벽 3개를 설치한 이후 0의 개수
	bool v[n][m]; //방문 확인 배열
	memset(v, false, sizeof(bool)*n*m); //방문 확인

	for(pair<int, int> i : two) q.push({i.first, i.second}); //바이러스인 곳을 전부 큐에 집어 넣고
	while(!q.empty()) { //bfs 실행
		int x = get<0>(Q);
		int y = get<1>(Q);
		q.pop();
			
		for(int j=0; j<4; j++) {
			x += V[j];
			y += H[j];
			if(x >= 0 && y >= 0 && x < n && y < m && Map[x][y]==0 && !v[x][y]) { //방문을 하지 않았으며 0인 곳이라면
				v[x][y] = true;
				--cnt;
				q.push({x, y});
			}
			x -= V[j];
			y -= H[j];
		}
	}
	
	
	if(Max < cnt) Max = cnt; //최대값보다 cnt이 크다면 cnt을 대입
}

//벽 설치하기
void loop(int N, int a, int b) { //브루트포스, N은 벽 설치한 개수, a와 b는 최근 설치한 벽의 위치 입니다.
	if(N == 3) { //세 개 설치한 경우
		bfs(); //bfs
		return;
	}
	
	for(int i=a; i<n; i++) { //벽 설치하기
		int j=0;
		if(N > 0 && i == a) j = b+1; //이전 벽보다 오른쪽으로
		for(j; j<m; j++) {
			if(Map[i][j] == 0) { //0인 곳에만 벽을 칠 수 있습니다.
				Map[i][j] = 1; //벽을 칩니다.
				if(N<3) loop(N+1, i, j); //새로운 벽을 치기
				Map[i][j] = 0; //벽을 다시 치웁니다 (다른 곳에 설치하기 위해)
			}
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	
	for(int i=0; i<n; i++)
	for(int j=0; j<m; j++)
	{
		int tmp = 0;
		cin >> tmp;
		Map[i][j] = tmp;
		if(tmp == 2) two.push_back({i, j});
		else if(tmp == 0) ++zero; //0의 개수 구하기
	}
	
	loop(0, 0, 0); //브루트포스 실행
	
	cout << Max;
}

 

풀이 : BFS + 브루트포스

 

들어가기 전에

using namespace std;

을 하게 되면 전역변수를 만들 때, max, map 같은 건 이미 std에 있는 것들이다 보니 이름을 다르게 해야합니다.

 

1. 브루트포스로 벽을 설치할 3 곳을 1로 바꾸어 줍니다. 중요한 점은 시간을 아끼기 위해서 처음 설치한 벽 보다 두번째로 설치한 벽은 더 오른쪽이나 아래에 있어야 하며, 두번째로 설치한 벽보다 세번째로 설치한 벽이 더 오른쪽이나 아래에 있어야 합니다.

 

 

void loop(int N, int a, int b) {
 if(N == 3) {
  bfs();
  return;
 }

 

 for(int i=a; i<n; i++) {
  int j=0;
  if(N > 0 && i == a) j = b+1;
  for(j; j<m; j++) {
   if(Map[i][j] == 0) {
    Map[i][j] = 1;
    if(N<3) loop(N+1, i, j);
    Map[i][j] = 0;
   }
  }
 }

}

 

이를 위해서 2중 for문에 약간의 조건문을 추가 했으며

벽을 세번 설치한 이후 bfs을 실행하도록 만들었습니다. //if(N == 3)

 

2. 큐에 2인 곳을 전부 다 넣은 다음 bfs을 돌려서 0의 개수를 구합니다.

 

3.  1, 2 을 반복하면서 0의 개수의 최대값을 구합니다.

 

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

14502번: 연구소