14502. 연구소

안전영역의 최대를 위해서 바이러스의 부분을 최소로 해야한다.

문제의 특성상 벽의 위치를 모두 고려해 여러 번 바이러스 연산을 통해 영역을 구해야하므로 따로 바이러스 위치를 저장하는 배열을 만들어 바이러스의 퍼지는 연산 전 queue를 채워 bfs를 연산할 수 있게 하였다.

벽의 위치는 조합의 연산을 이용하였고, 2중 for문에 대한 조합의 연산을 위해 조건문이 생겼다.

해당 조건문은 조합의 연산에서 그 전에 벽을 설치한 앞의 부분은 고려하지 않고 그 뒤의 배열 위치부터 고려하기 위함이다.

 

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

public class Main {

	static int birus = Integer.MAX_VALUE;
	static Queue<int[]> q = new LinkedList<int[]>();
	static List<int[]> list = new ArrayList<>(); // 바이러스의 위치
	static boolean[][] visited;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[][] arr = new int[N][M];
		int wallCnt = 3;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if (arr[i][j] == 2) {
					list.add(new int[] { i, j });
				} else if (arr[i][j] == 1)
					wallCnt++;
			}
		}

		wall(0, 0, 0, N, M, arr);

		int result = (N * M) - birus - wallCnt;
		System.out.println(sb.append(result));
	}

	private static int bfs(int N, int M, int[][] arr) {
		int cnt = 0;
		int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
		while (!q.isEmpty()) {
			cnt++;
			int[] now = q.poll();
			for (int i = 0; i < 4; i++) {
				int my = now[0] + dir[i][0];
				int mx = now[1] + dir[i][1];
				if (my < 0 || mx < 0 || my >= N || mx >= M || visited[my][mx])
					continue;
				visited[my][mx] = true;
				if (arr[my][mx] != 1) {
					q.offer(new int[] { my, mx });
				}
			}
		}
		return cnt;
	}

// 벽 세우기 -> 조합
	private static void wall(int cnt, int n, int m, int N, int M, int[][] arr) {
		if (cnt == 3) {
			visited = new boolean[N][M];
			makeQueue(); // 바이러스의 위치를 만든다
			int result = bfs(N, M, arr);
			birus = Math.min(result, birus);
			return;
		}
		for (int i = n; i < N; i++) {
			for (int j = 0; j < M; j++) {
 // 조합의 특성상(중복(1,2와 2,1은 같다)X -> 순서가 없기 때문에) 
 // 앞의 부분은 모두 연산이 끝난 상태로 선택한 벽의 위치 그 뒤에서 부터 벽에 대한 연산을 시작하기 위해
				if (i == n && j < m) { // 조건이 생김.
					continue;
				}
				if (arr[i][j] == 0) {
					arr[i][j] = 1;
					wall(cnt + 1, i, j, N, M, arr);
					arr[i][j] = 0;
				}
			}
		}
	}
    
// 바이러스의 연산을 위해 큐에 바이러스 위치를 넣어준다
	private static void makeQueue() { 
		int size = list.size();
		for (int i = 0; i < size; i++) {
			q.offer(list.get(i));
			visited[list.get(i)[0]][list.get(i)[1]] = true;
		}
	}
}