접근
설치한 벽의 개수가 3개가 되는 모든 조합에 대해,바이러스 확산을 진행하고 안전 영역의 크기를 계산해야 한다.
DFS vs BFS
DFS로 풀 경우
- dfs로 벽을 설치하면서, 바이러스를 확산 시키고, 매번 안전 영역의 크기를 계산한다.
BFS로 풀 경우
- 벽 설치는 dfs
- 바이러스 확산은 bfs
얕은 복사 vs 깊은 복사
- 깊은 복사를 하지 않고 얕은 복사(Shallow Copy)를 하게 되면 원래 그래프(graph)의 상태도 동시에 변경되어 원하지 않는 결과가 나올 수 있다.
- 여기서는 tmp 배열을 사용하여 바이러스 확산을 시뮬레이션하고, 그 결과를 기반으로 안전 영역의 크기를 계산
- 이때 tmp 배열은 graph 배열의 현재 상태를 복사하고, 그 이후에 tmp 배열을 변경하기 때문에 원래 그래프의 상태가 변경되지 않고 그대로 유지됨
해결
DFS로 풀기
바이러스 확산도 재귀적으로 하기 때문에 기준 좌표의 상하좌우 좌표중 바이러스가 확산될 수 있는 공간은 확산시키고, 해당 좌표에 대해 다시 spreadVirus()를 호출해야 하는 처음에 놓쳐서 안전 영역 크기가 답보다 크게 크게 나왔었다. 😅
import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static int n, m, result = 0;
public static int[][] graph = new int[8][8];
public static int[][] tmp = new int[8][8];
public static int[][] directions = {{-1,0}, {1,0}, {0,-1},{0,1}};
public static void spreadVirus(int x, int y) {
for (int[] d : directions) {
int nx = x + d[0];
int ny = y + d[1];
if (0 <=nx && nx< n && 0<=ny && ny<m) {
if (tmp[nx][ny] == 0) {
tmp[nx][ny] = 2;
spreadVirus(nx, ny); // 재귀적으로 바이러스 확산!!!
}
}
}
}
public static void dfs(int count) {
// 설치된 울타리가 3개인 경우 -> 현재 설치상태에서 바이러스 확산
if (count == 3) {
for (int i =0; i<n; i++) {
for (int j=0; j<m; j++) {
tmp[i][j] = graph[i][j];
}
}
// 바이러스 확산
for (int i =0; i<n; i++) {
for (int j=0; j<m; j++) {
if(tmp[i][j] == 2) {
spreadVirus(i, j);
}
}
}
int sum = 0;
// 안전영역 크기 갱신
for (int i =0; i<n; i++) {
for (int j=0; j<m; j++) {
if(tmp[i][j] == 0) {
sum += 1;
}
}
}
result = Math.max(sum, result);
}
// 설치된 울타리가 3개 미만인 경우 -> 울타리 하나씩 세워보기
else {
for (int i = 0; i<n; i++) {
for (int j = 0; j<m; j++) {
if (graph[i][j] == 0) {
graph[i][j] = 1;
count += 1;
dfs(count);
graph[i][j] = 0;
count -= 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());
// 그래프 입력
for (int i=0; i< n; i++) {
st = new StringTokenizer(br.readLine());
for (int j=0; j<m; j++){
graph[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0);
System.out.println(result);
}
}BFS로 풀기
import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.awt.Point;
public class Main {
public static int n, m, result = 0;
public static int[][] graph = new int[8][8];
public static int[][] tmp = new int[8][8];
public static int[][] directions = {{-1,0}, {1,0}, {0,-1},{0,1}};
public static void spreadVirus() {
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
Queue<Point> q = new LinkedList<>();
q.offer(new Point(i,j));
while(!q.isEmpty()) {
Point p = q.poll();
int x = p.x;
int y = p.y;
if (tmp[x][y] == 2) {
for (int[] d : directions) {
int nx = d[0] + x;
int ny = d[1] + y;
if (0 > nx || nx >= n || 0 > ny || ny >= m) {
continue;
}
if (tmp[nx][ny] == 0) {
tmp[nx][ny] = 2;
q.offer(new Point(nx,ny));
}
}
}
}
}
}
}
public static void dfs(int count) {
// 설치된 울타리가 3개인 경우 -> 현재 설치상태에서 바이러스 확산
if (count == 3) {
for (int i =0; i<n; i++) {
for (int j=0; j<m; j++) {
tmp[i][j] = graph[i][j];
}
}
// 바이러스 확산
spreadVirus();
int sum = 0;
// 안전영역 크기 갱신
for (int i =0; i<n; i++) {
for (int j=0; j<m; j++) {
if(tmp[i][j] == 0) {
sum += 1;
}
}
}
result = Math.max(sum, result);
}
// 설치된 울타리가 3개 미만인 경우 -> 울타리 하나씩 세워보기 (dfs)
else {
for (int i = 0; i<n; i++) {
for (int j = 0; j<m; j++) {
if (graph[i][j] == 0) {
graph[i][j] = 1;
count += 1;
dfs(count);
graph[i][j] = 0;
count -= 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());
// 그래프 입력
for (int i=0; i< n; i++) {
st = new StringTokenizer(br.readLine());
for (int j=0; j<m; j++){
graph[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0);
System.out.println(result);
}
}
대단해요!!! 😀😀😀😀😀