연구소

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

풀이생각

1. 일단 bfs
2. 벽을 3개 세운다?

소스코드

Main

	static int [] dx ={1,-1,0,0};
    static int [] dy = {0,0,1,-1};
    static int N,M;
    static int [][] arr;

    static int result = Integer.MIN_VALUE;
    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());

        arr = new int[N][M]; //그냥 지도

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine()," ");
            for (int j = 0; j < M; j++) {
               arr [i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0);;
        System.out.println(result);

    }

dfs

public static void dfs(int depth){
        // 벽 3개 있을 때
        if(depth == 3){
            bfs();
            return;
        }
        //벽 3개가 없을때
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(arr[i][j]==0){
                    arr[i][j]=1;
                    dfs(depth+1);
                    arr[i][j]=0;
                }
            }
        }
    }

bfs

static void bfs(){
        int [][] virus = new int[N][M];
        Queue<dot> q = new LinkedList();

        // arr 카피
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                virus[i][j] = arr[i][j];
            }
        }

        for (int i = 0; i <N ; i++) {
            for (int j = 0; j <M ; j++) {
                if(virus[i][j]==2){
                    q.add(new dot(i,j));
                }
            }
        }
        while(!q.isEmpty()){
           dot d = q.remove();
            //사방확인
            for (int i = 0; i < 4; i++) {
                int nx = d.x + dx[i];
                int ny = d.y + dy[i];
                //범위를 벗어나지 않는 선에서 바이러스
                if(0<=nx && 0<=ny && nx < N && ny < M){
                    if(virus[nx][ny]==0){
                        q.add(new dot(nx,ny));
                        virus[nx][ny]=2;
                    }
                    //바이러스 감염 된거?
                 }
                }
            }
        safe(virus);

        }

safe판단여부

 public static void safe(int[][]virus) {
    // 배열 중에 0 인곳만 카운트
    int cnt =0;

        for (int i = 0; i <N ; i++) {
            for (int j = 0; j <M ; j++) {
                if(virus[i][j]==0){
                    cnt++;
                }
            }
            }
        result = Math.max(result,cnt);
    }

풀이방법

1. dfs로 기둥 3개 완전탐색?
2. bfs로 상하좌우 탐색해서 virus구분
3. 안전구역 카운트

참고

https://dding9code.tistory.com/3