BOJ - 15812 ) 침략자 진아

---

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

1717번: 집합의 표현

---

맵의 모든 1의 개수가 정복되는 최소 시간을 구하는 것이므로

 

모든경우를 살펴야한다 ( 완전탐색 ) 

 

BFS를 이용하여, 1을 만날때마다 카운트를 증가시켜 전체의 1의 개수와 같아질때의 시간을 구한다.

 

모든경우의 수에서 최소시간이 정답이다  !

---

 

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


public class boj15182 {
	public static int space = 0;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new  StringTokenizer(br.readLine());
		int y = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());
		int map[][] = new int[y][x];
		
		for(int i=0;i<y;i++) {
			String str = br.readLine();
			for(int j=0;j<x;j++){
				map[i][j] = str.charAt(j) == '1' ? 1 : 0 ;
				// space 는  1의 개수 나중에 bfs돌리면서 찾은 1의 개수가 space랑 같으면 stop 
				if(map[i][j]==1){
               		 space++;
                   }
				}
		} // end of input
		
		ArrayDeque<int []> dq = new ArrayDeque<>();
		int dir[][] = {{1,0},{-1,0},{0,1},{0,-1}};
		int answer = 987654321;
		
		for(int i = 0 ;i < y ; i++) {
			for(int j= 0 ; j < x ; j++) {
				if(map[i][j] == 0) {
					for(int a = i ; a< y ; a++) {
						for(int b= j ; b< x ; b++) {
							if(i==a && j ==b)continue;
							if(map[a][b]==0) {
								// 서로 다름과 0 이 보장됨 두지점에서 bfs해서 최소시간 구하기 
								// 그냥 숫자를 체크하면 될듯
								
								int cmap[][] = new int[y][x];
								for(int z=0;z<y;z++)cmap[z] =map[z].clone();
								
								int time = 0;
								int kill = 0; 
								
								dq.add(new int[] {i,j}); cmap[i][j] = 2;
								dq.add(new int[] {a,b}); cmap[a][b] = 2;
								
								while(!dq.isEmpty()){
									time++;
									int size = dq.size();
									while(size-->0) {
										int now[] = dq.poll();
										for(int k=0;k<4;k++) {
											int ny = now[0] + dir[k][0];
											int nx = now[1] + dir[k][1];
											if(ny>=0&&nx>=0&&ny<y&&nx<x&&cmap[ny][nx]!=2) {
												if(cmap[ny][nx]==1) kill++;
												cmap[ny][nx]=2;
												dq.add(new int[] {ny,nx});
											}
										}
									}
									if(kill==space) break;
								}
								dq.clear();
								answer  = answer > time ? time : answer;
							}
						}
					}
				}
			}
		}
		System.out.println(answer);
	}
}

---