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

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

 

[풀이과정]

1.바이러스 걸린 방의 위치 저장 해 둔다, 여기서는 vector를 사용했다.

   배열을 사용해서 저장해도 되는데 사이즈를 따로 관리해야하는 번거로움이 있어서 vector를 이용했다.

   BFS에서 사용할 queue에 저장해서 넘겨주면 될 것 같지만 그렇게 되면 BFS가 한번 돌고 나면 queue에서 사라지므로 

   변형되지 않는 곳을 만들어서 저장해 두어야 한다.

2.3가지 종류의 벽의 조합을 모두 만들어야 하므로 DFS를 사용해야 한다.

3.벽을 만든 후에는 vector에 저장된 바이러스가 퍼지는 는 맵을 완성한다.

4.바이러스가 모두 퍼진 후 전염되지 않은 방의 갯수를 센다.

5.2번부터 다시 반복해서 바이러스가 전염되지 않은 방 갯수 중 가장 큰 경우를 찾으면 된다. 

 

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

int N,M;//행,열 
int map[8][8];
int tmp[8][8];//방문 표시
int dy[]={-1,1,0,0};//상하좌우
int dx[]={0,0,-1,1};
struct Q{
	int y,x;
};
queue<Q>q;
vector<Q>v;
int sol=0;
bool isInside(int a, int b){
	return ( (a>=0) && (a<N) && (b>=0) && (b<M));
}
int BFS(){	
	int count=0;
	//1.큐 초기화 
	q={};
	//2.큐에 초기값 입력 
    for(int i = 0; i < v.size(); i++)
        q.push(v[i]);
	//3.반복문 
	while(!q.empty()){
		Q cur=q.front();q.pop();
		for(int i=0; i<4; i++){
			int ny=cur.y+dy[i];
			int nx=cur.x+dx[i];
			if(isInside(ny,nx) && tmp[ny][nx]==0){
				tmp[ny][nx]=2;
				q.push({ny,nx});
			}	
		}
	}
	//4.return할 값 
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			if(tmp[i][j]==0)
				count++;
		}
	}
	return count;
}
void copymap(){
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			tmp[i][j]=map[i][j];
		}
	}
}
	
void DFS(int x, int d){
	if(d==3){
		copymap();//기존 map을 훼손하면 안되므로 임시 map에 저장함 
		sol=max(sol,BFS());//감염되지 않은 방중 최대값으로 업데이트 
		return;
	}
	for(int i=x; i<N; i++){
		for(int j=0; j<M; j++){
			if(map[i][j]==0){
				map[i][j]=1;
				DFS(i,d+1);
				map[i][j]=0;
			}
		}
	}

}
void Solve(){
	DFS(0,0);//맵에서 벽을 세울수 있는 경우를 DFS를 이용해서 조합으로 만듬
	cout<<sol<<endl;//오염되지 않은 방중 가장 큰값 
}
void InputData(){
	cin>>N>>M;
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			cin>>map[i][j];
			if(map[i][j]==2){
				v.push_back({i,j});//바이러스 걸린 방을 따로 저장해 두어야한다. 
			}
		}
	}
}
int main(){
	InputData();
	Solve();
	return 0;
}