[BOJ] 백준 14502 연구소

[문제]

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

 

 

[소스 코드]

import java.io.*;
import java.util.*;
public class Main {
	static int n,m;
	static int[][] map;
	static int result = 0; 
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,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());
		map = new int[n][m];
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<m;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		select(0);
		System.out.println(result);
	}
	private static void select(int cnt) {
		if(cnt==3) {
			int[][] copy = new int[n][m];
			for(int i=0;i<n;i++) {
				copy[i] = map[i].clone();
			}
			bfs(copy);
			return;
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(map[i][j]==0) {
					map[i][j] = 1;
					select(cnt+1);
					map[i][j] = 0;
				}
			}
		}
	}
	private static void bfs(int[][] copy) {
		Queue<int[]> q = new LinkedList<>();
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(copy[i][j]==2) {
					q.offer(new int[] {i,j});
				}
			}
		}
		while(!q.isEmpty()) {
			int[] curr = q.poll();
			for(int d=0;d<4;d++) {
				int nr = curr[0] + dr[d];
				int nc = curr[1] + dc[d];
				if(nr>=0 && nr<n && nc>=0 && nc<m && copy[nr][nc]==0) {
					copy[nr][nc] = 2;
					q.offer(new int[] {nr,nc});
				}
			}
		}
		int cnt = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(copy[i][j]==0) {
					cnt++;
				}
			}
		}
		result = Math.max(result, cnt);
	}
}