[BOJ 14502] 연구소

구현 자체는 어렵지 않았지만, 방법을 떠올리는 것이 어려웠던 문제.

BFS나 DFS를 이용하되, 바이러스가 있는 부분에서 BFS/DFS를 돌려서 바이러스를 퍼뜨린다는 생각의 전환(?) 이 필요한 문제

벽을 세울 수 있는 후보군을 뽑은 다음 3중 for문을 돌려서 각각의 경우의 수를 모두 판단해 주어야 해서 조금 난이도가 있었다ㅠㅠ... 

사실 질문란을 좀 베꼈다......ㅠㅠㅠㅠㅠㅠㅠㅠ 반성해야지 ㅠㅠ

처음에 망설인 이유가 3중 for문이라고? 그것보다 더 간단한 방법 없을까? 때문에 고민했던 건데

실제 시험에서는 1문제 당 90분이라고 생각하면 이렇게 여유롭게 생각할 시간도 많이 없을 것 같아서 다른 파트의 구현을 먼저 생각하는 것이 맞는 것 같다.

package samsung;

import java.util.*;

public class Num14502 {

	static int c_map[][];
	
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		
		int N = sc.nextInt() + 2;
		int M = sc.nextInt() + 2;
		
		int[][] map = new int[N][M];
		int[] qx = new int[N * M];
		int[] qy = new int[N * M];
		
		c_map = new int[N][M];
		
		int size = 0;
		
		for(int i = 0 ; i< N ; i++){
			map[i][0] = 1;
			map[i][M-1] = 1;
		}
		for(int i = 0 ; i< M ; i++){
			map[0][i] = 1;
			map[N-1][i] = 1;
		}
		
		
		for(int i = 1 ; i < N-1 ; i++){
			for(int j = 1 ; j < M-1 ; j++){
				map[i][j] = sc.nextInt();
				if(map[i][j] == 0){
					qx[size] = i;
					qy[size] = j;
					size++;
				}
			}
		}
		
		Queue vx = new LinkedList();
		Queue vy = new LinkedList();

		int num = 0;
		
		for(int i = 0 ; i< size - 2 ; i++){
			for(int j = i+1 ; j < size - 1 ; j++){
				for(int k = j+1 ; k < size ; k++){
					for(int p = 0 ; p < N ; p++){
						for(int q = 0 ; q < M ; q++){
							c_map[p][q] = map[p][q];
						}
					}
					
					c_map[qx[i]][qy[i]] = 1;
					c_map[qx[j]][qy[j]] = 1;
					c_map[qx[k]][qy[k]] = 1;
					
					for(int p = 0 ; p < N ; p++){
						for(int q = 0 ; q < M ; q++){
							if(c_map[p][q] == 2){
								vx.add(p); vy.add(q);
								while(!vx.isEmpty()){
									int x = vx.poll();
									int y = vy.poll();
									
									c_map[x][y] = 2;
									
									if(c_map[x-1][y] == 0){
										vx.add(x-1); vy.add(y);
									}
									if(c_map[x+1][y] == 0){
										vx.add(x+1); vy.add(y);
									}
									if(c_map[x][y-1] == 0){
										vx.add(x); vy.add(y-1);
									}
									if(c_map[x][y+1] == 0){
										vx.add(x); vy.add(y+1);
									}
								}
							}
						}
					}
					
					int cnt = 0;
					for(int p = 0 ; p < N ; p++){
						for(int q = 0 ; q < M ; q++){
							if(c_map[p][q] == 0){
								cnt++;
							}
						}
					}
					if(num < cnt){
						num = cnt;
					}
					
				}
			}
		}
		
		System.out.println(num);
		
		
	}
}