문제 이해

N X M 직사각형 배열이 주어진다.

0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다.
바이러스는 벽을 제외하고 상하좌우 인접한 모든 칸으로 퍼져나간다.

벽을 3개 새로 세워서 바이러스 확산을 최대한 막고 싶다.

꼭 벽 3개를 모두 설치해야할 때, 바이러스 확산이 안 되는 영역을 가장 크게 했을 때의 안전 영역 크기를 구하는 문제이다.

---

문제 풀이

처음엔 DP등의 방법으로 해결할 수 있지 않을까 생각했지만, 결국 Brute-Force와 DFS(혹은 BFS)를 통해 해결하는 방법밖에 생각이 나지 않았다.

그냥 벽 3개를 빈 공간에 설치할 수 있는 모든 경우의 수로 설치해보고, 그 때 DFS(or BFS)를 통해 안전 바이러스를 모두 퍼뜨린 뒤 안전 영역 개수를 구하면 된다.

참고로, List에 바이러스 시작 지점을 먼저 저장해놓아 조금이라도 Search 속도를 빠르게 했다.

---

코드

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<>();
    // Virus 위치
	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];
			}
		}
        // arr를 깊은 복사를 통해 배열을 만들어 줘야 함
		
		for(Sub s:wall_sub) {
        // 새로 세운 3개의 벽들을 설치함
			change[s.x][s.y] = 1;
		}
        
		Queue<Sub> queue = new LinkedList<>();
		
		for(Sub s:virus) {
        // 바이러스 시작점을 Queue에 담아서 BFS 시작
			queue.offer(s);
		}
		
		int zero = subs.size() - 3;
        // 아직 바이러스가 퍼지지 않은 지역
        // 아래 BFS 과정에서 바이러스가 퍼지면 zero 값이 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) {
    // 벽 3개를 세울 수 있는 모든 경우의 수를 찾는 메서드
		
		if(wall_sub.size()==3) { 
            // 벽 3개를 세웠으므로 BFS를 통한 Search 수행
			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();
		}
	}
	
	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));
				}
				else if(tmp==2) {
					virus.add(new Sub(i,j));
				}
			}
		}
		
		all_case(0, new LinkedList<Sub>());
		System.out.println(max);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과