BOJ 연구소2, 연구소3 #17141, 17142 JAVA

조합과 BFS를 연습할 수 있는 연구소 2, 3를 풀었다.

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

17141번: 연구소 2

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

17142번: 연구소 3

 

0. 0의 개수를 세서 전부 다 찼는지 검사할 수 있도록 한다.

1. combination로 N개의 바이러스중에 M개를 뽑는다.

2. 뽑은 M개의 바이러스를 BFS돌려서 최소 dist를 뽑아낸다.

 

2<->3 다른점은 바이러스가 활성으로 바뀌는 것 입니다.

바이러스가 퍼져서 다른 바이러스도 활성이 되면서 그 자리는 이미 퍼진것으로 간주해야합니다.

 

 

package BOJ;

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

public class 연구소2 {
	static int N; 
	static int M;
	static int[][] map;
	static int[][] mapCpy;
	static class Virus{
		int y,x,d;
		public Virus(int y, int x, int d) {
			this.y = y;
			this.x = x;
			this.d = d;
		}
	}
	static int zero = 0;
	static int ans = Integer.MAX_VALUE;
	static ArrayList<Virus> v = new ArrayList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		//1. dfs 경우의 수 찾고
		//2. bfs로 시간 찾고
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		mapCpy = new int[N][N];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 2) {
					v.add(new Virus(i,j,0));
				}else if(map[i][j]==0)zero++;
			}
		}
		
		recursive(0,0, new int[M]);
		if(ans == Integer.MAX_VALUE) {
			System.out.println(-1);
			return;
		}
		System.out.println(ans);
	}
	private static void recursive(int idx, int k, int sel[]) {
		if(k == sel.length) {
//			System.out.println(Arrays.toString(sel));
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					mapCpy[i][j] = map[i][j];
				}
			}
			int res = BFS(sel);
			if(res != -1) {
				ans = Math.min(res,ans);
			}
			
			return;
		}
		if(idx == v.size()) {
			return;
		}
		sel[k] = idx;
		recursive(idx+1, k+1, sel);
		recursive(idx+1, k, sel);	
	}
	static int dy[] = {0,0,-1,1};
	static int dx[] = {1,-1,0,0};
	private static int BFS(int[] sel) {
		boolean visited[][] = new boolean[N][N];
		int localZero = 0;
		ArrayDeque<Virus>adq = new ArrayDeque<>();
		for(int i=0; i<sel.length; i++) {
			Virus virus = v.get(sel[i]);
			visited[virus.y][virus.x]=true;
			adq.add(virus);
			//localZero++;
		}
		int max=0;
		while(!adq.isEmpty()) {
			Virus virus = adq.poll();
			int cy = virus.y;
			int cx = virus.x;
			int cd = virus.d;
			max = Math.max(max, cd);
			//System.out.println(cd);
			for(int i=0; i<4; i++) {
				int ny = cy +dy[i];
				int nx = cx +dx[i];
				if(check(ny,nx))continue;
				if(map[ny][nx]==1)continue;
				if(visited[ny][nx])continue;
				visited[ny][nx] = true;
				adq.add(new Virus(ny,nx,cd+1));
				localZero++;
			}
			
 		}
		//System.out.println(localZero +" "+zero);
		if(localZero-(v.size()-M) == zero) {
			return max;
		}
		return -1;
		
	}
	private static boolean check(int ny, int nx) {
		if(ny<0||ny>=N ||nx<0||nx>=N)return true;
		return false;
	}
}

 

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

public class  Main{
   //바이러스 : 활성, 비활성
   //바이러스를 활성상태로 바꿔서 퍼트리고 최소가 되는 시간
   //1초 
   static int N;
   static int M;
   static int[][] map;
   static int zeros= 0;
   static class Virus{
      int y, x, dist;
      Virus(int y, int x){
         this.y = y;
         this.x = x;
         
      }
   }
   static int ans = Integer.MAX_VALUE;
   //static Virus[] viruses; //몇개를 배열로 담을지 모르니까. 우선은 ArrayList로 관리해야함.
   static ArrayList<Virus> viruses = new ArrayList<>();
   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());
      map = new int[N][N];
      for(int i=0; i<N; i++) {
         st = new StringTokenizer(br.readLine());
         for(int j=0; j<N; j++) {
            map[i][j] = Integer.parseInt(st.nextToken());
            if(map[i][j] == 2)viruses.add(new Virus(i,j));
            if(map[i][j] == 0)zeros++; //맵에 존재하는 0의 수
         }
      }
      recursive(0,0,new int[M]);
      //0:빈칸
      //1:벽
      //2:바이러스
      //idea 1 : 바이러스의 조합을 골라야한다.
      //바이러스의 조합을 골라서 bfs를 하고 최소를 고른다.
      //그러려면? -> virus를 담는 객체가 필요하다.
      //512MB로 나름 널널한 메모리 복사를 맘껏해도 괜찮겠군.
      if(zeros==0) {
         System.out.println(0);
         return;
      }
      if(ans == Integer.MAX_VALUE) {
         System.out.println(-1);
         return;
      }
      System.out.println(ans);
   }
   private static void recursive(int idx, int k, int sel[]) {
      // TODO Auto-generated method stub
      if(k == sel.length) {
         //System.out.println(Arrays.toString(sel));
         
         int[][] tempMap = new int[N][N];
         for(int i=0; i<N; i++) {
            tempMap[i] = map[i].clone();
         }
         int res =BFS(sel, tempMap);
         if(res != -1)
            ans = Math.min(res, ans);
         return;
      }
      if(idx == viruses.size()) {return;}
      
      sel[k] = idx;
      recursive( idx+1,  k+1, sel);
      recursive( idx+1,  k, sel);
      
   }
   
   static int[] dy = {1,0,-1,0};
   static int[] dx = {0,1,0,-1};
   private static int BFS(int[] sel, int [][] map) {
      // TODO Auto-generated method stub
      ArrayDeque<int[]> adq = new ArrayDeque<>();
      boolean [][] visited = new boolean[N][N];
      
      for(int i=0; i<sel.length; i++) {
         int y = viruses.get(sel[i]).y;
         int x = viruses.get(sel[i]).x;
         visited[y][x] = true;
         adq.offer(new int[] {y,x,0}); 
         
      }
      
      int time =0;
      int count =0;
      while(!adq.isEmpty()) {
         int []curr = adq.poll();
         int dist = curr[2];
            time = Math.max(time, dist);
         for(int i=0; i<4; i++) {
            int ny = curr[0]+dy[i];
            int nx = curr[1]+dx[i];
            
            if(checkOutside(ny, nx))continue;
            if(visited[ny][nx])continue;
            
            if(map[ny][nx]==0) {
               visited[ny][nx]=true;
               //System.out.println(ny+" "+ nx);
               count++;
               if(count == zeros) {
            	   return dist+1;
               }
               adq.add(new int[] {ny,nx,dist+1});
            }else if(map[ny][nx]==2) {
               visited[ny][nx] = true;
               adq.add(new int[] {ny, nx, dist+1});
            }
            
         }
      }
      //print(map);
      //System.out.println(count);
      //System.out.println(zeros);

      return -1;
      
      
   }
   
   private static boolean checkOutside(int ny, int nx) {
      // TODO 밖인지 체크 밖이면 true 
      if(ny<0 || ny>=N || nx<0||nx>=N)return true;
      return false;
   }
   private static void print(int[][] m) {
      System.out.println();
      for (int i = 0; i < m.length; i++) {
         for(int j=0; j<m[i].length; j++) {
            System.out.print(m[i][j]+" ");
         }
         System.out.println();
      }
   }
}