[백준] 연구소 14502

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class boj14502 {

    /*
    1. 맵을 copy
    2. 재귀 함수를 통해 벽을 3개 세움
    3. 벽을 세운 카피 맵을 통해 bfs 진행해서 바이러스 진행
    4. 안전 영역을 구한 후 Math.max 를 통해 값 변경
    5. 모든 값을 비교 후 result 반환
     */
    static int n, m, result = 0;
    static int[][] map, copy;
    static boolean[][] visit;
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    static List<List<int[]>> com = 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][m];
        copy = new int[n][m];
        visit = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = copy[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        List<int[]> temp = new ArrayList<>();
        comb(copy,0,0, temp);

        for (List<int[]> a : com) {
            for (int[] b : a) {
                copy[b[0]][b[1]] = 1;
            }
            start(copy);
        }

        System.out.println(result);

    }

    public static void start(int[][] board){
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 2 && !visit[i][j]) {
                    bfs(new int[]{i, j}, board);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(board[i][j] == 0) count++;
            }
        }
        result = Math.max(result, count);
        init();
    }

    public static void comb(int[][] board, int x, int y, List<int[]> temp){
        if(temp.size() == 3){
            com.add(new ArrayList<>(temp));
            return;
        }

        for (int i = x; i < n; i++) {
            for (int j = (i == x ? y : 0); j < m; j++) {
                if(board[i][j] == 0){
                    temp.add(new int[]{i, j});
                    comb(board, i, j + 1, temp);
                    temp.remove(temp.size() - 1);
                }
            }
        }

    }

    public static void init(){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                copy[i][j] = map[i][j];
            }
        }
        visit = new boolean[n][m];
    }

    public static void bfs(int[] point, int[][] board){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(point);

        while (!queue.isEmpty()) {
            int[] p = queue.poll();
            int x = p[0];
            int y = p[1];

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if(board[nx][ny] == 1) continue;
                if ((board[nx][ny] == 0 || board[nx][ny] == 2) && !visit[nx][ny]) {
                    board[nx][ny] = 2;
                    visit[nx][ny] = true;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
    }
}