너무 반복을 많이 돌리나 싶어서 생각만 했던 방법인데, 다른 방법이 떠오르지않아 무작정 구현해보았는데 한번에 성공했다. 시간 복잡도에 대해서 공부를 더 해야 할거 같은 생각이 들었다.
연구소에 격벽을 3개 세워야 하는데 어디다가 세워야 할지를 한번에 딱 알 수 없으므로 모든 경우의 수에 대해서 격벽을 세우고 bfs를 통해서 바이러스가 증식되는지 확인하는 logic으로 접근했다.
벽이 3개니깐 크게는 삼중 for문을 사영했다.
i, j , k 를 사용하는 for문이며 i는 0부터, j는 i보다는 1큰값, k는 j보다 1큰값을 시작점으로 잡았으며, 가로와 세로를 곱한 크기만큼 반복을 돌도록 설정했다.
일직선이 아니라 2차원 배열의 형태이므로 몫,나머지를 이용해서 좌표를 설정할 수 있을것이라고 생각했다.
map[i/m][i%m]
map[i/m][i%m]가 0인 경우에만 격벽을 세울 수 있으므로 아닌경우는 continue를 처리했다.
i,j,k에 격벽을 다 세우면 그 상태를 똑같이 가지고 있는 dummy_map이라는 배열을 만들어서 dummy_map을 사용하여 bfs를 돌렸다.
여기서 2차원 배열은 직접 값을 대입하는 방법으로만 deepCopy가 되므로 메서드르 만들어서 해결했다.
public static int [][] deepCopy(int [][] dummy_map){ for(int e1=0; e1<n; e1++ ){ for(int e2=0; e2<m; e2++){ dummy_map[e1][e2]=map[e1][e2]; } } return dummy_map; }
또한 chk도 격벽 상태에 대한 bfs가 종료될때마다 초기화 해주었다.
public static void resetChk(){ for(int l=0; l<n; l++){ Arrays.fill(chk[l],false); } }
격벽에 대한 bfs가 종료될때마다 해당 dummy_map의 0의 개수를 체크하고 최댓값을 갱신한다.
public static void calc(int [][] dummy_map){ int zero_cnt=0; for(int i=0; i<n; i++){ for(int j=0; j<m;j++){ if(dummy_map[i][j]==0){ zero_cnt++; } } } answer = Math.max(answer,zero_cnt); }
해당 격벽에 대한 bfs가 전부 끝나면 그 격벽은 다시 0으로 바꾸고 다음 격벽을 세운다.
import java.util.*;
public class Main {
static int n;
static int m;
static boolean[][] chk;
static int [][] map;
static int[] diry = {-1, 0, 1, 0};
static int[] dirx = {0, 1, 0, -1};
static int answer = 0;
static class Node {
int y;
int x;
public Node(int y, int x) {
this.y = y;
this.x = x;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
map = new int[n][m];
chk = new boolean[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
map[i][j] = sc.nextInt();
}
}
for (int i = 0; i < n * m; i++) {
if(map[i/m][i%m]!=0){
continue;
}
map[i/m][i%m]=1;
for (int j = i + 1; j < n * m; j++) {
if(map[j/m][j%m]!=0){
continue;
}
map[j/m][j%m]=1;
for (int k = j + 1; k < n * m; k++) {
if(map[k/m][k%m]!=0){
continue;
}
map[k/m][k%m]=1;
int [][] dummy_map = new int[n][m];
dummy_map = deepCopy(dummy_map);
resetChk();
for(int p=0; p<n; p++){
for(int q=0; q<m; q++){
if(dummy_map[p][q]==2 && !chk[p][q]){
dummy_map = bfs(p,q,dummy_map);
}
}
}
calc(dummy_map);
map[k/m][k%m]=0;
}
map[j/m][j%m]=0;
}
map[i/m][i%m]=0;
}
System.out.println(answer);
}
public static int [][] deepCopy(int [][] dummy_map){
for(int e1=0; e1<n; e1++ ){
for(int e2=0; e2<m; e2++){
dummy_map[e1][e2]=map[e1][e2];
}
}
return dummy_map;
}
public static void resetChk(){
for(int l=0; l<n; l++){
Arrays.fill(chk[l],false);
}
}
public static int[][] bfs(int y, int x, int [][] dummy_map) {
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(y, x));
dummy_map[y][x] = 2;
chk[y][x] = true;
while (!queue.isEmpty()) {
Node now = queue.poll();
for (int i = 0; i < 4; i++) {
int now_y = now.y + diry[i];
int now_x = now.x + dirx[i];
if (now_y >= 0 && now_y < n && now_x >= 0 && now_x < m) {
if (!chk[now_y][now_x] && dummy_map[now_y][now_x] == 0) {
dummy_map[now_y][now_x] = 2;
chk[now_y][now_x] = true;
queue.add(new Node(now_y, now_x));
}
}
}
}
return dummy_map;
}
public static void calc(int [][] dummy_map){
int zero_cnt=0;
for(int i=0; i<n; i++){
for(int j=0; j<m;j++){
if(dummy_map[i][j]==0){
zero_cnt++;
}
}
}
answer = Math.max(answer,zero_cnt);
}
}