문제 이해

2는 virus, 0은 안전 구역, 1은 벽이다.
바이러스는 안전 구역을 오염시킬 수 있으며, 벽은 뚫지 못한다.
(즉, 2 1 0의 경우 0은 오염되지 않음)

이 때 벽을 딱 3개 세워 안전 구역을 최대한 크게 만들고 싶다.
이 때 안전 영역의 최대 크기(즉, 0의 최대 개수)를 출력하는 문제이다.

문제 풀이

계속해서 효율적인 방법을 고민해봤지만, 결국 벽을 모든 곳에 세워 보는 Brute-Force방법밖에 생각나지 않았다.
벽은 0에만 설치할 수 있으므로 모든 0에 설치해보고, 설치 이후 0의 개수를 세면 된다.

알고리즘 순서는 아래와 같다.

1. 0인 위치에 벽을 설치한다(값을 1로 바꿈)

2. Array에서 2를 찾고, 그 부분부터 DFS를 수행한다. 조금 더 자세히 표현하면 DFS를 통해 다다른 상하좌우 부분 중 값이 0인 곳을 오염시키고(2로 값을 변경시키고), 그 점에서 다시 DFS를 수행한다.

3. 1의 개수는 정해져 있다. 따라서 2로 오염시킬 때마다 count를 세어 2로 오염된 칸의 개수를 구하고, (전체 배열의 공간) - (1의 개수 + 2로 오염된 개수)를 통해 0의 개수를 구하고, 1,2,3 과정을 모든 0에 대해 반복하여 그 중 최댓값을 찾는다.

• Array의 원 형태는 계속해서 사용해야 하므로, 얕은 복사가 아닌 깊은 복사를 통해 만든 새로운 Array를 사용해야 한다.

코드

import java.io.*;
import java.util.*;

class Sub{
	int x;
	int y;
	public Sub(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int N,M;
	static int[][] arr;
	static ArrayList<Sub> subs = new ArrayList<>();
	static ArrayList<Sub> virus = new ArrayList<>();
	static int max = Integer.MIN_VALUE;
	
	static void bfs(LinkedList<Sub> wall_sub) {
		int[][] change = new int[N][M];
		
        // 깊은 복사를 위한 과정
		for(int i =0;i<N;i++) {
			for(int j =0;j<M;j++) {
				change[i][j] = arr[i][j];
			}
		}
		
        // 벽 3개를 추가로 세우는 과정
		for(Sub s:wall_sub) {
			change[s.x][s.y] = 1;
		}

		Queue<Sub> queue = new LinkedList<>();
		for(Sub s:virus) {
			queue.offer(s);
		}
		
		int zero = subs.size() - 3; 
        // 0의 개수. 2로 오염될 때 마다 1씩 감소할 것임

		while(!queue.isEmpty()) {
			Sub tmp = queue.poll();

			if(change[tmp.x][tmp.y]!=2) continue;
			
			if(tmp.x+1<N && change[tmp.x+1][tmp.y]==0) {
				zero--;
				change[tmp.x+1][tmp.y] = 2;
				queue.add(new Sub(tmp.x+1,tmp.y));
			}

			if(tmp.x-1>=0 && change[tmp.x-1][tmp.y]==0) {
				zero--;
				change[tmp.x-1][tmp.y] = 2;
				queue.add(new Sub(tmp.x-1,tmp.y));
			}

			if(tmp.y+1<M && change[tmp.x][tmp.y+1]==0) {
				zero--;
				change[tmp.x][tmp.y+1] = 2;
				queue.add(new Sub(tmp.x,tmp.y+1));
			}

			if(tmp.y-1>=0 && change[tmp.x][tmp.y-1]==0) {
				zero--;
				change[tmp.x][tmp.y-1] = 2;	
				queue.add(new Sub(tmp.x,tmp.y-1));
			}
			
		}
		max = Math.max(zero, max);
	}
	
	static void all_case(int index, LinkedList<Sub> wall_sub) {
		if(wall_sub.size()==3) { 
            // Search 수행(벽을 3개 세웠으므로 바이러스 확산 실행)
			bfs(wall_sub);
			return;
		}

		for(int i =index;i<subs.size();i++) {
			Sub tmp = subs.get(i);
			wall_sub.add(tmp); 
            // 벽 하나 세움
            
			all_case(i+1, wall_sub); 
            // 벽 하나를 세운 상태로 다음 벽 세우기 작업 수행
            
			wall_sub.removeLast(); 
            // 2번째 줄 전 세웠던 벽을 지우고 다음 0 위치에 벽을 세움
		}
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		M = sc.nextInt();
		
		arr = new int[N][M];

		int tmp;
		
		for(int i =0;i<N;i++) {
			for(int j =0;j<M;j++) {
				tmp = sc.nextInt();
				arr[i][j] = tmp;
				if(tmp==0) {
					subs.add(new Sub(i,j));
                    // 벽 위치를 매번 for문을 통해 찾지 말고, 
                    // 미리 다른 공간에 좌표를 저장해 놓았음
                    
                    // subs : 0 
                    // 좌표 : 오염되지 않은 공간 & 벽이 설치될 수 있는 공간
				}
				else if(tmp==2) {
                    // 바이러스 위치도 마찬가지로 매번 for문을 통해 찾지 말고 
                    // 좌표를 저장해 놓았음
                    
                    // virus : 2 
                    // 좌표 : 오염원의 좌표
					virus.add(new Sub(i,j));
				}
			}
		}
		
		all_case(0, new LinkedList<Sub>());
		System.out.println(max);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

결과