백준 [14502] 연구소
문제보기
풀이
- list에 바이러스 위치를 담고 buildWall()를 통해 벽이 3개가 세워지면 safeZone()에서 바이러스를 확산시키고 안전영역 갯수 확인.
- 주의사항 : queue가 다음 buildWall()에서 비어버린 상태가 아니도록 조심. 즉 queue를 같은 주소로 쓰는지 아닌지 확인.
소스코드
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N, M, safezone, ans;
static int[] dx = { 0, 0, -1, 1 };
static int[] dy = { -1, 1, 0, 0 };
static ArrayList<int[]> list;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
int[][] map = new int[N][M];
safezone = 0;
ans = 0;
list = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
map[i][j] = sc.nextInt();
if (map[i][j] == 2) {
list.add(new int[] { i, j });
} else if (map[i][j] == 0)
safezone++;
}
}
buildWall(0, map);
System.out.println(ans);
}
public static void buildWall(int cnt, int[][] map) {
if (cnt >= 3) {
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < list.size(); i++) {
queue.add(list.get(i));
}
safeZone(map, queue);
return;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0) {
map[i][j] = 1;
buildWall(cnt + 1, map);
map[i][j] = 0;
}
}
}
}
public static void safeZone(int[][] map, Queue<int[]> queue) {
int cnt = safezone - 3;
boolean[][] visited = new boolean[N][M];
while (!queue.isEmpty()) {
int[] q = queue.poll();
for (int k = 0; k < 4; k++) {
int x = q[0] + dx[k];
int y = q[1] + dy[k];
if (isRange(x, y) && map[x][y] == 0 && !visited[x][y]) {
visited[x][y] = true;
cnt--;
queue.add(new int[] { x, y });
}
}
}
ans = Math.max(ans, cnt);
}
public static boolean isRange(int x, int y) {
return x >= 0 && y >= 0 && x < N && y < M;
}
}