백준 17142 - 연구소

www.acmicpc.net/problem/17142

17142번: 연구소 3

문제 설명

---

바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다.

승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

M = 3, 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시.

 

[왼쪽 : 바이러스가 전염되는 예시] [중앙 : 바이러스, 벽, 공간 정보 좌표][오른쪽 : 전염의 최소시간]

시간이 최소가 되는 방법은 오른쪽 그림과 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

 

 

접근 방법

---

삼성 코테 기출문제 입니다. Bfs와 Brute Force를 이용했습니다. Virus에 대한 각각의 상황을 파악하기위해 Brute Force를 이용했고 바이러스가 정해지고 바이러스가 모두 퍼졌는지 또는 전체에 퍼질수없는 지에 대해 파악하기위해 Bfs를 사용했습니다.

DIRECTION

1. 처음 부터 벽, 바이러스, 전체 공간에 대한 정보를 변경해서 map을 업데이트 했습니다.

벽: -1

활성 바이러스(초기): 0

 비활성 바이러스: -2

빈공간: -3

2. 바이러스에 대한 정보를 개별적으로 저장 m만큼의 바이러스만 추출하여 사용하도록 Brute force를 이용

3. 선택된 바이러스를 Bfs를 통해 시간에 따른 전염을 시행

4. 시행후 최대 시간을 측정해서 저장. (단, 최대로 걸린 시간에 해당하는 공간이 바이러스가 위치한 공간이라면 제외한다.)

5.  3~4의 과정을 반복하면서 최소시간을 구한다.

 

 

코드

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int n,m,minTime=987654321;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
int map[51][51];
int temp_map[51][51];
vector<pair<int,int> >virus;
vector<pair<int,int> >active;
queue<pair<int,int> >q;
void copy(){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			temp_map[i][j]=map[i][j];
		}
	}
}
void solution(int idx,int cnt){
	if(cnt==m){
		copy();
		// -1: 벽 
		// -2: 비활성 바이러스 0:활성 바이러스
		// -3: 빈공간
		//chk virus state;
		for(int i=0;i<active.size();i++){
			q.push(make_pair(active[i].first,active[i].second));
		}
		while(!q.empty()){
			int cury = q.front().first;
			int curx = q.front().second;
			q.pop();
			for(int i=0;i<4;i++){
				int ny = cury+ dy[i];
				int nx = curx+ dx[i];
				if(ny>=0&&nx>=0&&ny<n&&nx<n){
					if(temp_map[ny][nx]==-3 || temp_map[ny][nx]== -2){
						//시간증가
						temp_map[ny][nx]= temp_map[cury][curx]+1;
						q.push(make_pair(ny,nx));
					}
				}
			}

		}
		int temp=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(temp_map[i][j]==-3) return;
				else if(temp < temp_map[i][j]){
					int flag=0;
                    //최대시간이 바이러스가 위치한 공간에 있으면 그 시간은 제외한다.(이미 바이러스가 존재하므로)
					for(int k=0;k<virus.size();k++){
						if(i==virus[k].first && j==virus[k].second){flag=1;break;}
					}
					if(flag==1) continue;
					else temp=temp_map[i][j];
				} 
			}
		}	
		//compare min
		minTime = min(minTime,temp);
		return;
	}
	for(int i=idx;i<virus.size();i++){

		int y = virus[i].first;
		int x = virus[i].second;
		map[y][x]=0;
		cnt++;
		active.push_back(make_pair(y,x));
		solution(i+1,cnt);
		active.pop_back();
		cnt--;
		map[y][x]=-2;
	}
}
// -1: 벽 
// -2: 바이러스 
// -3: 빈공간
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>map[i][j];
			if(map[i][j]==1) map[i][j]=-1;
			else if(map[i][j]==2) {map[i][j]=-2; virus.push_back(make_pair(i,j));}
			else map[i][j]=-3;
		}
	}
	solution(0,0);
	if(minTime==987654321)cout<<-1<<"\n";
	else cout<<minTime<<"\n";
	return 0;
}

funny algorithm 0_0 b