연구소3 (Java)

package Samsung;

import java.io.*;
import java.util.*;

public class 연구소3 {

	static int n,m;
	static StringTokenizer st;
	static int[][]arr;
	static ArrayList<Pair>virus;
	static boolean check[][];
	static boolean tmp[][];
	static int answer=Integer.MAX_VALUE;
	
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	
	static class Pair{
		
		int x,y;
		Pair(int x, int y){
			this.x =x;
			this.y = y;
		}
		
	}
	
	public static boolean cango(int x, int y) {
		
		return x>=0 && x<n && y>=0 && y<n;
	}
	
	public static int bfs(ArrayList<Pair>list) {
		
		Queue<Pair>q = new LinkedList<>();
		
		for(int t=0; t<list.size(); t++) {
			
			Pair p = list.get(t);
			q.add(p);
		}
		
		int time =0;
		
			while(!q.isEmpty()) {
				
				int sz =q.size();

				for(int i=0; i<sz; i++) {
				
				Pair pp =q.poll();
				int x = pp.x;
				int y = pp.y;
				
				
				for(int l=0; l<4; l++) {
					
					int nx =x+dx[l];
					int ny =y+dy[l];
					
					if(cango(nx,ny)&&arr[nx][ny]!=1) {
						
						//중요!! 
						if(check[nx][ny]==true && arr[nx][ny]==0)continue; //이미 체크되고 빈칸인경우는 탐색을 멈춘다
						if(arr[nx][ny]==2)arr[nx][ny]=0; // 바이러스는기존에 체크되었기 때문에 true라도 탐색을 더 진행한다
														 // 시간초과해결: 단 한번만 큐에넣고 탐색을 해야한다 그래서 한번 방문했을때 arr의 nx,ny를 0으로만들어 다시 탐색 하지 않도록한다
						q.add(new Pair(nx,ny));
						check[nx][ny]=true;
						
					}
				}
				
				if(checkAll()) {
					return time+1;
				}
				
				}	
				
				time++;
				
			}
			
	//		System.out.println(time);
			

				return -1;
			
		
	}
	
	public static boolean checkAll() {
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				
				if(arr[i][j]!=1 && check[i][j]==false) {
					return false;
				}
				
			}
		}
		
		return true;
	}
	
	public static void pick(int idx, ArrayList<Pair>list ) { //여러개의 바이러스중 m개의 바이러스를 고른다
		
		
		if(list.size()==m) {
			
			int res = bfs(list); // 모든 칸을 바이러스로 감염심키는데 필용한 시간
			check = new boolean[n][n]; //바이러스 감영여부를 알려주는 배열
			
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					check[i][j]=tmp[i][j];
					if(tmp[i][j])arr[i][j]=2; //기존의 바이러스를 0으로 만들었던것을 다시 2로 복구시킨다
				}
			}
			
			if(res==-1) return;
			answer = Math.min(res, answer );
			return;
			
		}
		
		for(int i=idx; i<virus.size(); i++) {
			
			list.add(virus.get(i));
			pick(i+1,list);
			list.remove(list.size()-1);
	
		}
		
	}
	
	
	public static void main(String[]args) throws IOException {
		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		check = new boolean[n][n];
		tmp= new boolean[n][n];
		arr = new int[n][n];
		virus = new ArrayList<>();
		
		for(int i=0; i<n; i++) {
			st =  new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				
				arr[i][j]=Integer.parseInt(st.nextToken());
				if(arr[i][j]==2) {
					virus.add(new Pair(i,j));
					check[i][j]=true;
					tmp[i][j]=true;
				}
			}
		
		}
		
		if(checkAll()) {  //바이러스가 이미 다 전파되었는지를 확인한다
			System.out.println(0);
			return;
		}
		
		pick(0,new ArrayList<>()); 
		
		if(answer == Integer.MAX_VALUE) {answer=-1;}
		System.out.println(answer);
		
		
	}
	
	
}

- 활성 바이러스가 아니었던게 활성이 되고나서 다시 해당 바이러스를 방문하지 않도록 처리해야 시간초과 안난다.