BOJ -17142 ) 연구소3

 

---

 

연구소 문제 시리즈 중 마지막이 아닐까? 바이러스의 개수 중 M개를 선택하여 BFS를 진행하면된다.

 

만약 처음에 선택되지 않은 바이러스를 중간에만나면 그 바이러스도 활성상태가되어 상하좌우 뻗어가는 문제이다.

 

비활성에서 활성으로 변할때 1초가 소요되므로 따로 처리해주지않고 진행한다.

 

맵에 더이상 진행할 곳이 없거나, 서브셋으로 선택하여도 바이러스로 모두 채울수 없을때에 해당 ANSWER값을 

 

출력한다.

---

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int answer = Integer.MAX_VALUE;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		ArrayDeque<int[]> dq = new ArrayDeque<int[]>();
		 int n = Integer.parseInt(st.nextToken()); 
		 int m = Integer.parseInt(st.nextToken());
		 int map[][] = new int[n][n];
		 ArrayList<int[]> virus_pos = new ArrayList<>();
		 for(int y = 0 ; y < n ; y++) {
			 st = new StringTokenizer(br.readLine());
			 for(int x = 0 ; x < n ; x++) {
				 map[y][x] = Integer.parseInt(st.nextToken());
				 if(map[y][x]==2) virus_pos.add(new int[] {y,x,0});
				 // arraylist에서 M개를 선택하고 큐에 넣는다.
			 }
		 }
		 
		 int vsize= virus_pos.size();
		 int cnt; int count[] = new int[vsize];
		 int dir[][] = {{1,0},{-1,0},{0,-1},{0,1}};
		 int res =0;
		 
		 for(int i =1, size = (1<<vsize) ; i < size ; i++){
			 cnt =0;
			 for(int j = 0 ; j < vsize ; j++) {
				 if((i&(1<<j)) != 0) {
					 cnt++;
					 count[j] =1;
				 }
				 else count[j]=0;
			 }
			 if(cnt == m) { // 바이러스에 대한 SUBSET을 구한다.
				 res =0;
				 boolean visit[][] = new boolean[n][n];
				 for(int index = 0 ; index < vsize ; index++) {
					 if(count[index] !=0) { 
						 int y =virus_pos.get(index)[0]; // y 좌표
						 int x =virus_pos.get(index)[1]; // x 좌표
						 visit[y][x] = true;
						 dq.add(new int[] {y,x,0});
                         // 선택된 바이러스만 DQ에 넣어준다.
					 }
				 }
				 
				 while(!dq.isEmpty()) {
					 int now[] = dq.poll();
					 int nowy = now[0];
					 int nowx = now[1];
					 if(map[nowy][nowx]==0) {
						 res = Math.max(res, now[2]);
                         // 시간업데이트는 현재가 활성& 비활성 바이러스가 아닐때만 진행
					 }
					 for(int index = 0; index <4 ; index++) {
						 int nexty = nowy + dir[index][0];
						 int nextx = nowx + dir[index][1];
						 if(nexty >=0 && nextx >=0 && nextx < n && nexty < n) {
							 if(map[nexty][nextx] != 1 && !visit[nexty][nextx]) {
								 visit[nexty][nextx] = true;
								 dq.add(new int[] {nexty, nextx,now[2]+1});
							 }

						 }
					 }
				 }	 
				
				 for(int y= 0; y<n ; y++) {
					 for(int x = 0; x<n ; x++) {
						 if(map[y][x] ==0 && !visit[y][x]) res = -1;
					 }
				 }
				 if(res>=0) answer = Math.min(answer, res);
				 
			 }
		 }
		 if(answer == Integer.MAX_VALUE) answer = -1;
		 System.out.print(answer);
	}

}

 

---