[Java] BOJ14502_연구소

www.acmicpc.net/problem/14502

14502번: 연구소

---

특별한 알고리즘으로 벽을 최적의 위치에 놓을 방법이 없기 때문에 브루트 포스로 벽을 다 세워봐야 한다. 지도의 최대 크기가 64이고 벽은 3개밖에 세우지 않으므로 충분히 시간 안에 가능하다.

 

값이 0인(빈 칸)곳의 위치를 리스트에 담아두고 조합을 이용하여 3개씩 뽑아냈다.

해당 위치에 벽을 세운 임시 배열을 만들고 값이 2인(바이러스) 위치에서 BFS를 통해 바이러스를 퍼뜨렸다.

바이러스를 다 퍼뜨리고 0의 갯수를 세서 최댓값 비교를 통해 결과에 담아주었다.

 

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

public class Main {

	static int N, M;
	static int[][] map;
	static boolean[][] visit;
	static ArrayList<point> empty = new ArrayList<>();
	static int res = Integer.MIN_VALUE;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		visit = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				int temp = Integer.parseInt(st.nextToken());
				map[i][j] = temp;
				if(temp == 0) empty.add(new point(i,j));
			}
		}
		combination(0, new point[3], 0);
		System.out.println(res);
	}

	public static void combination(int startidx, point[] result, int cnt) {
		
		if(cnt == 3) {
			int[][] tempArr = new int[N][M];
			for(int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					tempArr[i][j] = map[i][j];
				}
			}
			for(int i = 0; i < 3; i++) {
				tempArr[result[i].x][result[i].y] = 1;
			}
			boolean[][] tempVisit = new boolean[N][M];
			for(int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					tempVisit[i][j] = visit[i][j];
				}
			}
			int sum = 0;
			for(int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if(tempArr[i][j] == 2 && !tempVisit[i][j]) {
						bfs(i, j, tempArr, tempVisit);
					}
				}
			}
			
			for(int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if(tempArr[i][j] == 0) {
						sum++;
					}
				}
			}
			res = Math.max(res, sum);
			return;
		}
		
		for(int i = startidx; i < empty.size(); i++) {
			result[cnt] = empty.get(i);
			combination(i+1, result, cnt+1);
		}
	}
	
	private static void bfs(int r, int c, int[][] arr, boolean[][] visit) {
		
		Queue<int[]> q = new LinkedList<int[]>();
		q.offer(new int[] {r, c});
		visit[r][c] = true;
		
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			
			for(int i = 0; i < 4; i++) {
				int nr = temp[0] + dr[i];
				int nc = temp[1] + dc[i];
				
				if(nr < 0 || nc < 0 || nr >= N || nc >= M || visit[nr][nc]) continue;
				
				if(arr[nr][nc] == 0) {
					q.offer(new int[] {nr, nc});
					visit[nr][nc] = true;
					arr[nr][nc] = 2;
				} else if(arr[nr][nc] == 2) {
					q.offer(new int[] {nr, nc});
					visit[nr][nc] = true;
				}
			}
		}
	}

	public static class point{
		int x,y;

		public point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}