[Algorithm] 백준 알고리즘 14502 (연구소)

 

java 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Lab {

	static int N, M;
	static int map[][];
	static int virusMap[][];
	static boolean visited[];
	static ArrayList<int[]> qWall = new ArrayList<>();
	static int result;
	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];
		virusMap=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());
				if(map[i][j]==0) {
					qWall.add(new int[] {i, j});
				}
			}
		}
		visited=new boolean[qWall.size()];
		dfsWall(0, 0);
		
		System.out.println(result);
	}
	static void dfsWall(int n, int m) {		// 벽을 세우는 모든 경우의 수를 만들기 위한 dfs
		if(n==3) {
			for(int a=0; a<N; a++) {
				for(int b=0; b<M; b++) {
					virusMap[a][b]=map[a][b];
				}
			}
			for(int a=0;a<qWall.size();a++) {
				if(visited[a]) {
					virusMap[qWall.get(a)[0]][qWall.get(a)[1]]=1;
				}
			}
			bfs();
			return;
		}
		for(int i=m; i<qWall.size();i++) {
			if(!visited[i]) {
				visited[i]=true;
				dfsWall(n+1, i);
				visited[i]=false;
			}
		}
	}
	static void bfs() {
		Queue <int []> q = new LinkedList<>(); 
		int dx[] = {-1, 1, 0, 0};
		int dy[] = {0, 0, -1, 1};
		int count=0;
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(virusMap[i][j]==2) {
					q.add(new int[] {i, j});
				}
			}
		}
		while(!q.isEmpty()) {
			int location[]=q.poll();
			int x = location[0];
			int y = location[1];
			for(int i=0; i<4; i++) {
				int xx=x+dx[i];
				int yy=y+dy[i];
				if(xx>=0&&xx<N&&yy>=0&&yy<M) {
					if(virusMap[xx][yy]==0) {
						virusMap[xx][yy]=2;
						q.add(new int[] {xx,yy});
					}
				}
			}
		}
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(virusMap[i][j]==0) {
					count++;
				}
			}
		}
		result = Math.max(result, count);
	}
}