[BOJ] 14502. 연구소 - java

⬛ [BOJ] 14502. 연구소 - java

https://www.acmicpc.net/problem/14502

14502번: 연구소

⬛ 문제 정리

• 0은 빈칸, 1은 벽, 2는 바이러스
• 바이러스(2)는 벽을 통과할 수 없고 빈칸(0)으로만 확산된다.
• 꼭 3개의 벽을 세워야 하고 벽을 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다.
• 안전 영역 크기의 최댓값을 구하여라.

⬛ 풀이 방법

• map을 채울 때 빈칸(0)의 개수를 센다. -> zeroCnt
• dfs를 이용하여 3개의 벽을 세우는 완전 탐색 진행 -> setWall()
• 3개의 벽을 채운 뒤 bfs를 이용하여 바이러스(2)를 확산시킴 -> diffusion()
• boolean 배열 visited를 이용하여 바이러스(2)가 확산된 곳을 체크
• 빈칸(0) -> 바이러스(2)로 바뀔 때마다 cnt--

위와 같이 벽을 세웠을 때 안전 영역 크기의 최댓값 9를 가진다.

⬛ 소스 코드

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

public class BOJ_14502_연구소 {
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	static int zeroCnt, max, N, M;
	static int[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);
		map = new int[N][M];
		zeroCnt = 0;
		max = 0;
		for (int i = 0; i < N; i++) {
			input = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(input[j]);
				if (map[i][j] == 0)
					zeroCnt++;
			}
		}
		zeroCnt -= 3;
		setWall(0);
		System.out.println(max);
	}

	public static void setWall(int cnt) { // 3개의 벽을 채우고 확산시켜본 후 0의 개수의 최댓값을 계산 //dfs
		if (cnt == 3) {
			int result = diffusion();
			max = max < result ? result : max;
			return;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0) {
					map[i][j] = 1;
					setWall(cnt + 1);
					map[i][j] = 0;
				}
			}
		}
	}

	public static int diffusion() { // 확산 //bfs

		int cnt = zeroCnt;
		boolean[][] visited = new boolean[N][M]; // map을 바꾸지 않고 0->2로 확산된 애들을 체크
		Queue<int[]> queue = new LinkedList<>();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 2) {
					visited[i][j] = true;
					queue.offer(new int[] { i, j });
				}
			}
		}
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0];
			int c = cur[1];
			for (int i = 0; i < 4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc] == 0 && !visited[nr][nc]) { // 0이고 아직 2로 바뀌지 않은 것들만
					visited[nr][nc] = true; // 2로 바뀐 애들은 visited처리
					cnt = cnt - 1;
					queue.offer(new int[] { nr, nc });
				}
			}
		}
		return cnt;
	}
}