[ 백준 ][ 자바 ][ 14502 ] 연구소

하 뭐지...

풀긴했는데 8달전에 푼거보다 메모리랑 시간이 더 결렸다.

...

당황스럽다..ㅋㅋㅋ

코드는 작아지긴 했는데

솔직히 이번에 다시풀때 집중이 안돼서 너무 힘들었다,..ㅠ

이 문제는 

벽세우기가 다인 문제다.

 

벽 세우고, (dfs)

바이러스 뿌리고, (bfs) 

세면 된다.

이거를 반복시킨다.

원상복구할때 그거를 잘못생각해서 한참 해맸는데

비슷한 유형 문제를 몇번 풀어보면 될듯싶다.

package back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Virus{
	int y;
	int x; 
	Virus(int y, int x){
		this.y = y;
		this.x = x;
	}
}
public class Main_backjoon_14502_연구소 {
	static int[][] MAP = new int[9][9];
	static boolean VISITED[][] = new boolean[9][9];
	static Queue vq = new LinkedList();
	static Queue tempQ = new LinkedList();
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };
	static int N;
	static int M;
	static int solve = 0;
	static int allPlaceNum =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());
		for(int i = 0 ; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int index = 0;
			while(st.hasMoreTokens()) {
				MAP[i][index] = Integer.parseInt(st.nextToken());
				index++;
			}
		}
		risingWall(0);
		System.out.println(solve);
	}
	public static void risingWall(int depth) {
		if( depth == 3) {
			virusSpread(copyMap());
			return;
		}
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(MAP[i][j] == 0 ) {
					MAP[i][j] = 1;
					risingWall( depth + 1 );
					MAP[i][j] = 0;
				}
			}
		}
		
	}
	public static int[][] copyMap() { //원 상 복 귀 
		int[][] TEMP = new int[N][M];
		allPlaceNum = 0;
		for(int i = 0 ; i < N; i++) {
			for(int j = 0; j < M; j++) {
				TEMP[i][j] = MAP[i][j]; // 오리지날 맵 복사 
				if(TEMP[i][j] == 0 ) {
					allPlaceNum += 1;
				}
				if(TEMP[i][j] == 2) {
					vq.add(new Virus(i,j));
				}
			}
		}
		return TEMP;
	}
	
	public static void virusSpread(int[][] map) {
		int count = 0;
		while(!vq.isEmpty()) {
			Virus virus = vq.poll();
			for(int i = 0 ; i < 4; i++) {
				int yy = dy[i] + virus.y;
				int xx = dx[i] + virus.x;
				if( yy >= 0 && yy < N && xx >= 0 && xx < M) {
					if( map[yy][xx] == 0 && map[yy][xx] != 1) {
						vq.add(new Virus(yy,xx));
						map[yy][xx] = 2;
						count += 1;
					}
				}
			}
		}
		if(solve < allPlaceNum - count){
			solve = allPlaceNum - count;
		}
	}
}