[JAVA] 백준 14502 연구소

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

---

풀이: 브루트포스, bfs

구현이 복잡할 것 같았는데 다행히도 부루트포스였다. 벽이 존재할 수 있는 위치가 3군데에다가, 영역의 최대 개수가 64개이므로 64C3 = 41664번의 루프면 모든 경우를 고려할 수 있다.

1. 벽을 놓을 수 있는 위치를 리스트에 따로 저장한다.
2. 조합을 이용해서 리스트에서 3개의 위치를 선택하는 모든 경우의 수를 고려한다.
3. 경우의 수마다 bfs로 바이러스 전파 시뮬레이션을 수행한다.

---

코드

package baekjoon.gold.g5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class p14502연구소 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int[] com = new int[3];
	static int c;
	static int[][] map;
	static ArrayList<int[]> candidate;
	static ArrayList<int[]> virus;
	static int height;
	static int width;
	static int[] di = new int[]{0, 0, 1, -1};
	static int[] dj = new int[]{1, -1, 0, 0};
	static int minimum = Integer.MAX_VALUE;
	
	static void bfs() {
		boolean[][] visited = new boolean[height][width];
		Queue<int[]> queue = new LinkedList<int[]>();
		for(int[] v : virus) {
			visited[v[0]][v[1]] = true;
			queue.add(v);
		}
		while(!queue.isEmpty()) {
			int[] curr = queue.poll();
			for(int i=0; i<4; i++) {
				int ni = curr[0] + di[i];
				int nj = curr[1] + dj[i];
				if(ni>=0 && ni < height && nj >= 0 && nj < width && !visited[ni][nj] && map[ni][nj] == 0) {
					visited[ni][nj] = true;
					queue.add(new int[] {ni, nj});
				}
			}
		}
		int sum = 0;
		for(int i=0; i<height; i++) {
			for(int j=0; j<width; j++) {
				if(visited[i][j]) {
					sum += 1;
				}
			}
		}
		if(sum<minimum) {
			minimum = sum;
		}
	}
	
	static void combi(int cnt, int index) {
		if(cnt == 3) {
			for(int co: com) {
				map[candidate.get(co)[0]][candidate.get(co)[1]] = 1;
			}
			bfs();
			for(int co: com) {
				map[candidate.get(co)[0]][candidate.get(co)[1]] = 0;
			}
			return;			
		} else {
			for(int i=index; i<c; i++) {
				com[cnt] = i;
				combi(cnt +1, i+1);
			}
		}
	}
	public static void main(String[] args) throws IOException {
		String[] input = br.readLine().split(" ");
		height= Integer.parseInt(input[0]);
		width = Integer.parseInt(input[1]);
		map = new int[height][width];
		candidate = new ArrayList<>();
		virus = new ArrayList<>();
		
		for(int i=0; i< height; i++) {
			input = br.readLine().split(" ");
			for(int j=0; j<width; j++) {
				if(input[j].equals("0")) {
					map[i][j] = 0;
					candidate.add(new int[]{i, j});
				} else if(input[j].equals("2")) {
					map[i][j] = 2;
					virus.add(new int[] {i,j});
				}else {
					map[i][j] = 1;
				}
			}
		}
		
		c= candidate.size();
		combi(0, 0);
		System.out.println(candidate.size() + virus.size() - 3 - minimum);
	}
}