[Java]백준 BaekJoon.AC 14502 : 연구소 (너비우선탐색-bfs, 브루트포스 알고리즘)

 

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

 

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

public class Main {
	static int N, M;
	static int[][] arr;
	static int mxs = 0;
	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());
		
		arr = new int[N][M];
	
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		bf(0);
		
		System.out.println(mxs);
	
	}
	
	public static void bf(int num) {
		
		if(num==3) {
			virus();
			return;
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(arr[i][j]==0) {
					arr[i][j]=1;
					bf(num+1);
					arr[i][j]=0;
				}
			}
		}
		
	}
	
	public static void virus() {
		Queue<Dot> queue = new LinkedList<>();
		int[][] temp = new int[N][M];
		
		for(int i=0; i<N; i++) 
			for(int j=0; j<M; j++) temp[i][j] = arr[i][j];
		
		
		for(int i=0; i<N; i++) 
			for(int j=0; j<M; j++) 
				if(temp[i][j]==2) queue.add(new Dot(i, j));
		
		
		int[] col = {-1, 1, 0, 0}; //up,down,lef,rig
		int[] row = {0, 0, -1, 1};
		while(!queue.isEmpty()) {
			Dot dot = queue.poll();
			
			for(int i=0; i<4; i++) {
				int virusC = dot.col + col[i];
				int virusR = dot.row + row[i];
				
				if(virusC>=0 && virusC<N && virusR>=0 && virusR<M) {
					if(temp[virusC][virusR] == 0){
						temp[virusC][virusR] = 2;
						queue.add(new Dot(virusC, virusR));
					}
				}
				
			}
			
		}
		
		
		int max = 0;
		for(int i=0; i<N; i++) 
			for(int j=0; j<M; j++) 
				if(temp[i][j]==0) max++;
			
		
		if(mxs < max) mxs = max;
		
	}
	
	
}

class Dot{
	int col;
	int row;
	
	Dot(int col, int row){
		this.col = col;
		this.row = row;
	}
}