14502 연구소

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
public class Test {
	static int N,M;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,1,-1};
	static int answer = Integer.MIN_VALUE;
	public static void main(String[] args) throws IOException{ 
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		int[][] map = new int[N][M];
		
		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());
			}
		}
		
		makeWall(0,map);

		bw.write(answer+"\n");
		bw.flush();
		bw.close();
	}
	
	static void makeWall(int count,int[][] map) {
		if(count==3) {
			spreadVirus(map);
			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(count+1,map);
					map[i][j]=0;			
				}
			}
		}
	}
		
	static void spreadVirus(int[][] arr) {
		int[][] map = new int[N][M]; //새로운 map
		
		Queue<Point> q = new LinkedList<>();
		
		//바이러스 q에 넣기
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				map[i][j]=arr[i][j];
				if(map[i][j]==2) {
					q.add(new Point(i,j));
				}
			}
		}
		//2면 바이러스 상하좌우로 퍼뜨리기
		while(!q.isEmpty()) {
			Point p = q.poll();
			
			for(int i=0; i<4; i++) {
				int nx = p.x + dx[i];
				int ny = p.y + dy[i];
				
				if( nx<0 || ny<0 || nx>=N || ny>=M || map[nx][ny]!=0) continue;
				
				map[nx][ny] = 2;
				q.add(new Point(nx,ny));
			}
		}
		//안전 구역 세기
		answer = Math.max(answer,countSafeArea(map));
	}
	
	static int countSafeArea(int[][] map){
		int count =0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j]==0) {
					count++;
				}
			}
		}
		return count;
	}	
}

class Point{
	int x;
	int y;
	
	Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}

 

바이러스를 뿌릴 때 복사 배열을 하나 만들어서 해야하는 걸 생각하지 못했다

으이9 . .. 😶‍🌫️