0 빈칸, 1 벽, 2 바이러스의 위치
바이러스가 빈칸을 통해 퍼져나간다. 바이러스가 퍼질 수 없는 영역을 안전 영역이라고 한다.
이때 벽을 3개 추가로 세워 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하라.
현재 map 상태에서 바이러스를 퍼트린 다음 0의 개수를 세면 된다.
바이러스는 DFS나 BFS를 사용해서 퍼트리면 될 것이다.
문제는 벽을 3개 추가해야 한다는 것이다.
N, M 의 최대 값이 8이기 때문에 완전탐색을 사용해도 될 것 같다.
- 0인 곳을 3곳 선택해 벽을 세운다.
- 바이러스를 퍼트린다.
- 0인 지점의 수를 센다.
이 과정이 3중 루프 동안 반복이 되는 것이다.
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static FastReader scan = new FastReader();
static int N, M;
static int[][] map;
static int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static List<int[]> VIRUS;
static List<int[]> ZEROS;
static int safeZone = Integer.MIN_VALUE;
static void input() {
N = scan.nextInt();
M = scan.nextInt();
map = new int[N][M];
ZEROS = new ArrayList<>();
VIRUS = new ArrayList<>();
for (int row = 0; row < N; row++) {
for (int col = 0; col < M; col++) {
map[row][col] = scan.nextInt();
if (map[row][col] == 0) {
ZEROS.add(new int[]{row, col});
}
else if (map[row][col] == 2) {
int[] virus = new int[]{row, col};
VIRUS.add(virus);
}
}
}
}
static void bfs( int[][] map) {
Queue<int[]> q = new LinkedList<>();
for (int[] virus : VIRUS) {
q.add(virus);
}
while (!q.isEmpty()) {
int[] now = q.poll();
for (int d = 0; d < 4; d++) {
int nr = now[0] + DIRECTION[d][0];
int nc = now[1] + DIRECTION[d][1];
if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if (map[nr][nc] != 0) continue;
map[nr][nc] = 2;
q.add(new int[]{nr, nc});
}
}
}
static void renewSafeZone(int[][] map) {
int count = (int)Arrays.stream(map).flatMapToInt(Arrays::stream)
.filter(num -> num == 0)
.count();
safeZone = Math.max(safeZone, count);
}
static void buildWall(int i, int j, int k, int[][] map) {
map[ZEROS.get(i)[0]][ZEROS.get(i)[1]] = 1;
map[ZEROS.get(j)[0]][ZEROS.get(j)[1]] = 1;
map[ZEROS.get(k)[0]][ZEROS.get(k)[1]] = 1;
}
static int[][] deepCopy(int[][] map) {
return Arrays.stream(map)
.map(int[]::clone)
.toArray(int[][]::new);
}
public static void main(String[] args) {
input();
for (int i = 0; i < ZEROS.size() - 2; i++) {
for (int j = i + 1; j < ZEROS.size() - 1; j++) {
for (int k = j + 1; k < ZEROS.size(); k++) {
int[][] copyMap = deepCopy(map);
buildWall(i, j, k, copyMap);
bfs(copyMap);
renewSafeZone(copyMap);
}
}
}
System.out.println(safeZone);
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws FileNotFoundException{
br = new BufferedReader(new FileReader(s));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
'Algorithm > BOJ' 카테고리의 다른 글
| BOJ 14888 - 연산자 끼워넣기 (1) | 2024.10.10 |
|---|---|
| BOJ 14503 - 로봇 청소기 (2) | 2024.10.10 |
| BOJ 14501 - 퇴사 (1) | 2024.10.09 |
| BOJ 14500 - 테트로미노 (1) | 2024.10.09 |
| BOJ 14499 - 주사위 굴리기 (1) | 2024.10.09 |