[백준] 14502번 연구소 (bfs, 구현)

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

class Pos{ //좌표값을 가지는 클래스 
	int y; int x;

	public Pos(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}
	
}

public class Main {
	static int n,m;
	static int[][] map;
	static List<Pos> list=new ArrayList<Pos>();
	static boolean vis[]; //벽을 세운 곳
	static boolean check[][];//copy배열 방문 여부 체크
	static int[] ypos= {0,0,1,-1};
	static int[] xpos= {1,-1,0,0};
	static int answer;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		map=new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j]=sc.nextInt();
				if(map[i][j]==0)list.add(new Pos(i,j));//0의 좌표=벽세우는곳
			}
		}
		vis=new boolean[list.size()];
		comb(0,0);
		System.out.println(answer);
	}
	private static void comb(int cnt,int start) {
		if(cnt==3) {// 세운데 벽 세움 bfs 고
			bfs();
			return;
		}
		
		for (int i = start; i < list.size(); i++) {
			if(vis[i])continue;
			vis[i]=true;
			comb(cnt+1,i+1);
			vis[i]=false;
		}
	}
	private static void bfs() {
		
		int[][] copy=copyMap(); //복사한 배열을 받는다.
		check=new boolean[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(!check[i][j] && copy[i][j]==2) {// 바이러스 퍼진다아아
					Queue<Pos> q=new LinkedList<Pos>();
					q.add(new Pos(i,j));
					check[i][j]=true;
					while(q.size()!=0) {
						Pos cur=q.poll();
						int y=cur.y;
						int x=cur.x;

						for (int k = 0; k < 4; k++) {
							int yy=y+ypos[k];
							int xx=x+xpos[k];
							if(xx<0 || yy<0 || xx>=m || yy>=n)continue;
							if(check[yy][xx])continue;
							if(copy[yy][xx]!=1) {//0이거나 2인 경우 
								check[yy][xx]=true;
								copy[yy][xx]=2;//2로 만들어줌
								q.add(new Pos(yy,xx));
							}
						}
					}
				}
			}
		}
		int cnt=0;
		for (int i = 0; i < n; i++) {// 최종 0의 개수 세기
			for (int j = 0; j < m; j++) {
				if(copy[i][j]==0)cnt+=1;
			}
		}

		if(cnt>answer)answer=cnt;
		
	}
	private static int[][] copyMap() {//이차원 배열 복사해준다.
		int temp[][]=new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp[i][j]=map[i][j];
			}
		}
		
		for (int l = 0; l < list.size(); l++) {
			if(vis[l]) {//벽인 부분은 1로 만들어준다.
				int ty=list.get(l).y;
				int tx=list.get(l).x;
				temp[ty][tx]=1;
			}
		}
		
		
		return temp;
	}
}