[백준 14502] 연구소 java

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

문제

안전 영역이 최대가 되도록 벽 3개를 세웠을 때의 안전 영역 크기 구하기.
0: 빈칸
1: 벽
2: 바이러스
바이러스는 상하좌우 인접한 빈칸으로 퍼져 나갈 수 있으며 벽을 만나면 멈춘다.



문제 예제 2번의 경우 

빨간색 위치에 벽을 세우고 나면 바이러스가 초록색 칸들로 퍼진다.

이후 남은 0의 개수는 9개가 된다.

풀이 방법

벽 3개를 세우는 모든 경우에서 안전 영역의 크기를 계산해서 최대 안전 영역의 크기를 계산한다.

1. 벽 3개를 세운다.
2. 바이러스가를 전파 시킨다.
3. 빈칸(안전영역)의 크기를 센다.

코드

처음엔 안전 영역이 여러개 나오면 그 중 가장 큰 안전 영역의 값이 답인줄 알았는데
그런게 아니고 그냥 지도 전체에서 0의 개수만을 세어주면 되는것이었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_14502_연구소 {
    static int N,M;
    static int[][] map;
    static boolean[][] visited;
    static boolean[][] checked;
    static int res;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, 1, 0, -1 };

    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];
        visited = 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]= Integer.parseInt(st.nextToken());
            }
        }

        dfs(0,0,0);
        System.out.println(res);

    }


    private static void dfs(int L, int x, int y) {
        if(L==3) {
            find();
            return;
        }

        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {
                if(!visited[i][j]&&map[i][j]==0) {
                    visited[i][j]=true;
                    map[i][j]=1;
                    dfs(L+1,i,j);
                    map[i][j]=0;
                    visited[i][j]=false;
                }
            }
        }
    }


    private static void find() {

        checked =  new boolean[N][M];
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {
                if(!checked[i][j]&& map[i][j]==2) {
                    virus(i,j);
                }
            }
        }
        int size = 0;
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {
                if(!checked[i][j]&& map[i][j]==0) size++;
            }
        }
        res= Math.max(res, size);
    }


    private static void virus(int x,int y) {
        Queue<int[]> Q = new LinkedList<>();
        checked[x][y]= true;
        Q.offer(new int[] {x,y});
        while(!Q.isEmpty()) {
            int[] now = Q.poll();
            for(int i=0;i<4;i++) {
                int nx = now[0]+dx[i];
                int ny = now[1]+dy[i];
                if(nx<0||nx>=N||ny<0||ny>=M||checked[nx][ny] ||map[nx][ny]==1) continue;
                checked[nx][ny]=true;
                Q.offer(new int[] {nx,ny});
            }
        }

    }
}