문제
https://www.acmicpc.net/problem/14502
풀이
- N*M 연구소
- 빈 칸 or 벽
- 일부 칸은 바이러스 존재
- 상하좌우 인접한 빈 칸으로 퍼짐
- 벽을 3개 세울 수 있음
- 벽을 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라 함
- 안전영역 크기의 최댓값
다음과 같은 흐름으로 문제를 접근하면 쉽게 해결할 수 있습니다.
- 벽을 세울 수 있는 모든 곳에 3개씩 다 세우며
- 3개를 세웠다면 바이러스를 퍼트리고
- 퍼트린 후 안전영역의 개수를 파악하고 이를 업데이트하면 됩니다.
벽을 세울 수 있는 모든 곳에 세워야 최댓값을 파악할 수 있기 때문에, 재귀를 이용해 벽을 다 세워 봤습니다.
후에, BFS를 통해 바이러스를 퍼트리고 안전 영역의 개수를 파악했습니다.
입력
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];
virus = new ArrayList<>(); // 바이러스 시작 지점
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 2) virus.add(new int[] { i, j }); // 바이러스 위치 저장
}
}map: 연구실virus: 바이러스의 시작 지점- 바어리스의 시작 지점을 알아야 큐에 넣은 후 BFS를 진행할 수 있습니다.
벽 세우기
private static void makeWall(int wall) {
if (wall == 3) { // 3개 세웠다면 (기저조건)
bfs(); // 바이러스 퍼트리기
return;
}
// 모든 좌표 탐색
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 0) { // 벽을 세울 수 있다면
map[i][j] = 1;
makeWall(wall + 1); // 재귀
map[i][j] = 0; // 재귀 종료 후 원복 (백트래킹)
}
}
}
}wall: 세운 벽의 개수- 벽을 세운 후 3개를 세웠다면 탐색을 진행하므로, 탐색을 마친 후에는 벽을 세웠던 좌표를 원상복구해야 합니다.
(그래야 다음 좌표에 벽을 세우고 다시 탐색 가능)
바이러스 퍼트리기
private static void bfs() {
// 임시 맵
int[][] tmp = new int[n][m];
for (int i = 0; i < n; i++) tmp[i] = Arrays.copyOf(map[i], map[i].length); // 원본 복사
Queue<int[]> queue = new ArrayDeque<>();
for (int[] v : virus) queue.add(v); // 바이러스 위치 큐에 삽입
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int r = cur[0], c = cur[1];
// 4방 탐색
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) continue; // 범위 밖이면 continue
if (tmp[nr][nc] == 0) { // 빈 공간이라면 퍼트림
tmp[nr][nc] = 2;
queue.add(new int[] { nr, nc });
}
}
}
counting(tmp);
}- 원본 맵을 바이러스로 감염시키면, 다시 원상복구하기 힘들기 때문에 임시 맵을 생성하여 시뮬레이션을 진행했습니다.
- 탐색을 마친 후에는 이 맵을 들고 안전 영역의 개수를 파악했습니다.
안전 영역 개수
private static void counting(int[][] tmp) {
int cnt = 0; // 안전 영역 개수
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (tmp[i][j] == 0) ++cnt;
}
}
answer = Math.max(answer, cnt); // 최댓값 갱신
}- 전체 배열을 순회하며, 안전 영역(0)의 개수를 파악했습니다.
출력
answer = 0;
makeWall(0);
System.out.println(answer);
}
}answer를 0으로 초기화 후 탐색 시작- 탐색을 마치면
answer출력
코드
import java.io.*;
import java.util.*;
public class Main {
static int n, m, answer;
static int[][] map;
static List<int[]> virus;
static final int[] dr = { -1, 1, 0, 0 };
static final int[] dc = { 0, 0, -1, 1 };
private static void makeWall(int wall) {
if (wall == 3) {
bfs();
return;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 0) {
map[i][j] = 1;
makeWall(wall + 1);
map[i][j] = 0;
}
}
}
}
private static void bfs() {
int[][] tmp = new int[n][m];
for (int i = 0; i < n; i++) tmp[i] = Arrays.copyOf(map[i], map[i].length);
Queue<int[]> queue = new ArrayDeque<>();
for (int[] v : virus) queue.add(v);
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int r = cur[0], 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) continue;
if (tmp[nr][nc] == 0) {
tmp[nr][nc] = 2;
queue.add(new int[] { nr, nc });
}
}
}
counting(tmp);
}
private static void counting(int[][] tmp) {
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (tmp[i][j] == 0) ++cnt;
}
}
answer = Math.max(answer, cnt);
}
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];
virus = new ArrayList<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 2) virus.add(new int[] { i, j });
}
}
answer = 0;
makeWall(0);
System.out.println(answer);
}
}
