[BOJ] 백준 14502 - 연구소 (JAVA)

조합 + BFS 문제

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main14502_연구소 {
    private static int[] dx= {-1 , 0 , 1 ,0};
    private static int[] dy = {0, -1, 0, 1};
    private static ArrayList<Pair> list;
    private static ArrayList<Pair> virusPos;
    private static int[][] map;
    private static int[][] map2;
    private static Pair[] set ;
    private static int N;
    private static int M;
    private static int maxNum = Integer.MIN_VALUE;
    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());
        map = new int[N][M]; // 기본 lap 정보
        map2 = new int[N][M]; // 매번 3가지 벽을 세우고 virus()함수가 호출되는데 호출될때마다 초기화 해줘야됨.
        list = new ArrayList<>(); // 처음에 0의 위치를 저장함 
        virusPos = new ArrayList<>(); // 바이러스의 위치 저장
        set = new Pair[3]; //새로 세워진 3가지 벽의 위치
        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());
                if(map[i][j] == 0) {
                    list.add(new Pair(i,j));
                }
                
                if(map[i][j] ==2) {
                    virusPos.add(new Pair(i, j));
                }
                
            }
        }
        
        comb(0,0);        
        System.out.println(maxNum);
    }
    
    
    public static void comb(int idx, int k) {
        if(idx ==3) {
        
            virus(set);
            return;
        }
    
        for (int i = k; i < list.size(); i++) {
            set[idx] = new Pair(list.get(i).x, list.get(i).y);
            comb(idx+1, i+1);
        
        }
        
        
    }
    
    public static void virus(Pair[] set) {
        arrayCopy(map, map2);
        map2[set[0].x][set[0].y] = 1;
        map2[set[1].x][set[1].y] = 1;
        map2[set[2].x][set[2].y] = 1;        
        Queue<Pair> q = new LinkedList<>();
        for (int i = 0; i < virusPos.size(); i++) {            
            q.add(new Pair(virusPos.get(i).x, virusPos.get(i).y));
        }
        
        while(!q.isEmpty()) {
            Pair p = q.poll();
            for (int i = 0; i < dx.length; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if(nx >=0 && ny>=0 && nx< N && ny < M && map2[nx][ny] ==0) {
                    map2[nx][ny] = 2;
                    q.add(new Pair(nx, ny));
                }
            }
        }
        
        int result = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(map2[i][j] ==0) {
                    result ++;
                }
            }
        }
        maxNum = maxNum < result ? result : maxNum ;
        
        
        
        
        
        
    }
    
    public static void arrayCopy(int[][] array, int[][] copyarray) {
        for (int i = 0; i < N; i++) {
            copyarray[i] = array[i].clone();
        }
    }
    
    static class Pair{
        int x ;
        int y ;
        public Pair(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
        
    }
}