[백준 14502] 연구소

 

문제에 알고리즘 힌트가 있다.

연구소 크기가 최대 8*8 이다. => 완전탐색 가능

인접한 위치로 바이러스가 퍼진다 => 그래프

 

이러한 이유로 완전탐색 + BFS 로 풀었다.

 

풀이는 다음과 같이 진행했다.

1. 연구소 배열에 벽을 세운다.

2. BFS 로 바이러스를 퍼트린다.

3. 빈 칸의 개수를 세어 최대값을 저장한다.

4. 반복한다.

 

백트래킹을 활용해본 적이 없어서 벽을 세우는 방법이 좀 까다로웠다.

 

 

public class Main {
    
    static int n;
    static int m;
    static int a[][];
    static int temp[][];
    static int max = 0;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        m = sc.nextInt();
        a = new int[n][m];
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                a[i][j] = sc.nextInt();
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(a[i][j] == 0) {
                    a[i][j] = 1;
                    setWall(1);
                    a[i][j] = 0;
                }
            }
        }
        System.out.println(max);
    }
    
    public static void setWall(int cnt) {
        if(cnt == 3) {
            bfs();
            return;
        }
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(a[i][j] == 0) {
                    a[i][j] = 1;
                    setWall(cnt + 1);
                    a[i][j] = 0;
                }
            }
        }
    }
    
    public static void bfs() {
        temp = new int[n][m];
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                temp[i][j] = a[i][j];
        
        Queue<Pair> q = new LinkedList<Pair>();
        
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                if(temp[i][j] == 2)
                    q.offer(new Pair(i, j));
        
        int dx[] = {-1, 0, 1, 0};
        int dy[] = {0, -1, 0, 1};
        
        while(!q.isEmpty()) {
            int size = q.size();
            
            while(size-->0) {
                Pair p = q.poll();
                int px = p.x;
                int py = p.y;
                for(int i=0; i<4; i++) {
                    int mx = px + dx[i];
                    int my = py + dy[i];
                    if(0 <= mx && mx < n && 0 <= my && my < m) {
                        if(temp[mx][my] == 0) {
                            temp[mx][my] = 2;
                            q.offer(new Pair(mx, my));
                        }
                    }
                }
            }
        }
        max = max(max, checkZero());
    }
    
    public static int checkZero() {
        int cnt = 0;
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                if(temp[i][j] == 0)
                    cnt++;
        return cnt;
    }
    
    public static int max(int a, int b) {
        return a > b ? a : b;
    }
    
    static class Pair {
        int x;
        int y;
        
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}