BOJ14502_연구소

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
// class 사용계속 해보기!!
class Wall {
    int r;
    int c;
 
    public Wall(int r, int c) {
        super();
        this.r = r;
        this.c = c;
    }
}
 
public class Main {
 
    private static int N;
    private static int M;
    private static ArrayList<Wall> list; // Wall객체형태의 ArrayList
    private static int[][] map;
    private static Queue<Integer> q;
    private static int cnt_zero;
    private static int max;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new ArrayList<>();
 
        map = new int[N][M];
        map_clone = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                int number = Integer.parseInt(st.nextToken());
                map[i][j] = number;
                if (map[i][j] == 0) { // 조합을 돌리기 위해 list에 0인 위치를 넣음
                    list.add(new Wall(i, j));
                }
            }
        }
        // 벽 3개 둘곳 정하기 , 0인 위치가 10개라면 10C3
        comb(0, 0, 3); // 0조합을 담을 리스트에 넣을 인덱스, list에서 빼올 인덱스, 3이 뽑을 갯수
        System.out.println(max);
 
    } // end of main
 
    static ArrayList<Wall> aList = new ArrayList<>(); // 뽑은 조합을 담을 리스트
    static int[][] map_clone;
    
    private static void comb(int cnt, int t, int limit) {
        
        if (cnt == limit) { // 한개의 조합이 나오는 경우
            // map복제본에 계속 복사해서 map_clone을 사용
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    map_clone[i][j] = map[i][j];
                }
            }
            // map_clone에서 0인부분에 벽을 세우기
            for (int i = 0; i < aList.size(); i++) {
                int r = aList.get(i).r;
                int c = aList.get(i).c;
                // 벽세우고
                map_clone[r][c] = 1;
            }
            
            // 바이러스 퍼트리기
            q = new LinkedList<>();
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    if (map_clone[j][k] == 2) {
                        q.add(j);
                        q.add(k);
                    }
                }
            }
            bfs();
            
            // 0인부분 cnt_zero++
            cnt_zero = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if(map_clone[i][j] == 0) {
                        cnt_zero++;
                    }
                }
            }
            if(max < cnt_zero) {
                max = cnt_zero;
            }
            return;
        }
        for (int i = t; i < list.size(); i++) {
            aList.add(list.get(i));
            comb(cnt + 1, i + 1, limit);
            aList.remove(aList.size() - 1);
        }
    } // end of comb
 
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { -1, 0, 1, 0 };
 
    private static void bfs() {
 
        while (!q.isEmpty()) {
            int qx = q.poll();
            int qy = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = qx + dx[i];
                int ny = qy + dy[i];
                if (nx >= 0 && nx < N && ny >= 0 && ny < M && map_clone[nx][ny] == 0) {
                    map_clone[nx][ny] = 2;
                    q.add(nx);
                    q.add(ny);
                }
            }
        }
 
    } // end of bfs
} // end of class