[백준] C++ 17141번(연구소 2)

 

바이러스를 놓을 수 있는 칸에 바이러스를 놓아 최소한의 시간에 모두 감염시키는 문제이다.

 

문제 해결 방법

1. 바이러스를 놓을 수 있는 칸의 조합을 구해야 한다.(순열 XX 조합 OO)

2. 조합 별로 모두 BFS를 해서 최솟값을 구한다.

 

입력이 이렇게 들어오면

 

바이러스 조합이 될 수 있는 모든 경우의 수에 대해 BFS를 해서 가장 적게 걸리는 조합을 찾으면 된다!

만약 모든 조합에 대해 바이러스를 퍼뜨릴 수 없다면 -1을 출력.

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

int arr[51][51];
int arr2[51][51];
vector <pair<int,int> > V;

int row[4]={0,0,-1,1};
int col[4]={-1,1,0,0};
int min1=987654321;

void DFSandBFS(int count, int start);

int N=0;
int M=0;

int vi=0;

int main(void)
{
	cin>>N>>M;
	
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			cin>>arr[i][j];	
			if(arr[i][j]==2)
			{
				V.push_back(make_pair(i,j));
				vi++;
			}
			else
			{
				arr2[i][j]=arr[i][j];
			}
		}
	}
	
	DFSandBFS(0,0);
	
	if(min1==987654321)
	{
		cout<<-1;
	}
	else
	{
		cout<<min1;
	}
	
	return 0;
}

int result[11];

void DFSandBFS(int count, int start)
{
	if(count==M)
	{
		queue<pair<int,int> > Q;
		queue<int> Q2;
		
		int temp[51][51]={0};
		int visited[51][51]={0};
		
		for(int i=0; i<N; i++)
		{
			for(int j=0; j<N; j++)
			{
				temp[i][j]=arr2[i][j];
			}
		}
		for(int i=0; i<M; i++)//바이러스 위치를 결정함.(조합)
		{
			int num1=V[result[i]].first;
			int num2=V[result[i]].second;
			temp[num1][num2]=2;
			visited[num1][num2]=1;
			Q.push(make_pair(num1,num2));
			Q2.push(0);
		}
		
		int time=0;
		while(!Q.empty())
		{
			int num1=Q.front().first;
			int num2=Q.front().second;
			time=Q2.front();
			Q.pop();
			Q2.pop();
			
			for(int i=0; i<4; i++)
			{
				if(temp[num1+row[i]][num2+col[i]]==0&&visited[num1+row[i]][num2+col[i]]==0&&num1+row[i]>-1&&num1+row[i]<N&&num2+col[i]>-1&&num2+col[i]<N)
				{
					Q.push(make_pair(num1+row[i],num2+col[i]));
					Q2.push(time+1);
					visited[num1+row[i]][num2+col[i]]=1;
				}
			}
		}
		int sig=0;
		for(int i=0; i<N; i++)//방문되지 않은 곳을 확인하는 작업 
		{
			for(int j=0; j<N; j++)
			{
				if(temp[i][j]==0)
				{
					if(visited[i][j]!=1)
					{
						sig=1;
					}
				}
			}
		}
		if(sig==0&&time<min1)//전부 방문했다면?? 
		{
			min1=time;
		}
	}
	else//조합을 만든다. 
	{
		for(int i=start; i<vi; i++)//strat를 통해 작은 값을 탐색하지 않음으로 중복되는 조합을 피함.  
		{	
			result[count]=i;//조합을 만들 때는 vistied가 필요 없음 큰 거만 보기 때문에 
			DFSandBFS(count+1,i+1);//순열을 만들 때는 visited가 필요함. 
			result[count]=0;
		}
	}
}