📍 문제 설명
💡 접근
이코테에서 풀었던 문제다. 이코테에 있던 코드가 메모리 측면에서 5배 정도 좋게 나왔다.
이유는 벽을 세울 때 마다 값을 복사하는 배열을 생성해주어서였다..
👩💻 코드
import java.util.*;
public class Main {
static int n, m, h, k, answer,cnt, max, min, wall, result;
static int[][] board, clone;
static int[] visited = new int[100001];
static int[] parent = new int[100001];
static int[] ch,pm, combi;
static boolean flag = false;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static HashSet<String> set = new HashSet<>();
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
n = kb.nextInt();
m = kb.nextInt();
board = new int[n][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
board[i][j] = kb.nextInt();
}
}
//0 빈칸, 1 벽, 2 바이러스 위치
//일단 벽을 무조건 3개 채우고 나서 바이러스 전파시키기
T.solution(0, 0, 0);
System.out.println(result);
}
private void solution(int x, int y, int wall) {
//벽을 3개 세웠으면 2인 지점에 대해서 상하좌우로 바이러스 전파
if(wall == 3) {
clone = new int[n][m];
//배열값 복사
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
clone[i][j] = board[i][j];
}
}
//바이러스 전파
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(clone[i][j] == 2) {
virusSpread(i, j, clone);
}
}
}
//안전 영역 계산
result = Math.max(result, getScore());
}
//벽 세우기
else {
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(board[i][j] == 0) {
board[i][j] = 1;
solution(0,0, wall+1);
board[i][j] = 0;
}
}
}
}
}
private int getScore() {
int score = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (clone[i][j] == 0) {
score += 1;
}
}
}
return score;
}
private void virusSpread(int x, int y, int[][] clone) {
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx>=0 && ny>=0 && nx<n && ny<m && clone[nx][ny] == 0) {
clone[nx][ny] = 2;
virusSpread(nx, ny, clone);
}
}
}
}