[백준 14502번] 연구소- java

문제 설명

1. 연구소의 크기 NxM , 바이러스 2, 벽 1, 빈칸 0을 입력받는다.

2. 바이러스는 위아래양옆으로 퍼지고, 벽으로 막혀있으면 더 퍼지지 않는다.

3. 우리는 벽을 꼭 3개를 세워야 한다.

3. 바이러스가 모두 퍼진 후, 남은 빈칸의 최대 갯수를 츨력하면 된다.

풀이 과정

 1. 더 효율적인 방법을 찾고 싶었지만, 결국 매우 비효율적인 방법으로 풀게 되었다.

 2. 완전탐색과 BFS를 동시에 사용하였다.

 3. 먼저 벽을 3개를 세우는 모든 방법을 구하고, 3개가 세워졌으면 BFS를 진행하면 된다.

 4. 그리고 BFS가 끝날 때 마다 최대 크기를 구하면 된다.

 

코드

import java.util.*;

public class Main {
	public static int xMove[] = {-1, 1, 0, 0};
	public static int yMove[] = {0, 0, -1, 1};
	public static int lab[][];
	public static int labWall[][];
	public static int N;
	public static int M;
	public static Queue<coordinate> virusMove = new LinkedList<>();
	public static int ans = 0;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();

		lab = new int[N][M];    // 처음 입력받은 연구소
		labWall = new int[N][M]; // 벽을 세운 뒤
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++){
				lab[i][j] = sc.nextInt();   // 처음 연구소 위치를 입력받는다.
			}
		}
		DFS(0);     // BFS DFS모두 섞어서 풀어야한다.
		
		System.out.println(ans);
	}
	
	public static void DFS(int cnt) {
		if(cnt == 3) {    // 벽을 3개 세우면 BFS시도
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					int input = lab[i][j];  
					labWall[i][j] = input;      // 벽을 세운 map위치를 입력받고
					if(input==2) virusMove.add(new coordinate(i, j));   // 바이러스 위치 큐에 입력
				}
			}
			while(!virusMove.isEmpty()) {
				coordinate cor = virusMove.remove();    // 큐값을 하나씩 뺴가면서
				for(int i=0; i<4; i++) {    // 모든 위치에 대해 BFS시도..
					int toX = cor.x+xMove[i];
					int toY = cor.y+yMove[i];
					if(toX<0 || toY<0 || toX>=N || toY>=M) continue; // 여기서 나는 return으로 하는 바람에 자꾸 안돼서 이상했다... 나가면 for문만 안해주면 됨.
					if(labWall[toX][toY]==0) {      // 아직 퍼지지 않은 공간이면
						labWall[toX][toY] = 2;      // 바이러스 퍼진다.
						virusMove.add(new coordinate(toX, toY)); // 여긴 퍼진곳이니까 또 여기서부터 퍼져나간다.
					}
				}
			}
			int count = 0;      // 위의 while이 끝나면 모든 map에 바이러스가 퍼진 것이 끝난다.
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					if(labWall[i][j] == 0) count++;   // 그럼 안전 영역 숫자를 구한다.
				}
			}
			ans = Math.max(ans,  count);    // 최대 안전 영역 구하기
			return;
		}
		
		for(int i=0; i<N; i++) {    // 3개 세우는 모든 경우를 탐색한다. 사실 완전탐색으로 보면 될 듯.
			for(int j=0; j<M; j++) {
				if(lab[i][j]==0) {
					lab[i][j] = 1;
					DFS(cnt+1);
					lab[i][j] = 0;
				}
			}
		}
		
	}
	
}

class coordinate {    // 좌표 class
	int x;
	int y;
	
	coordinate(int x, int y){
		this.x = x;
		this.y = y;
	}
}