[백준] 14502번:연구소 (Java 자바)

문제

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

14502번: 연구소

 

 

풀이 및 소스코드

 

조합(combi) 을 통해서 세울 벽 3개를 고르는 경우의 수를 구한 후, 그에 대해 bfs를 진행해서 바이러스를 퍼뜨려주었다.

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;

class Main {
	static int n,m,b;
	static int[][] map;
	static node[] select = new node[3];
    //세울 3개의 벽을 선택하는 경우가 담길 배열
	static int res = 0;
	static ArrayList<node> virus = new ArrayList<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = 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]==2) {
					virus.add(new node(i,j));
				}else if(map[i][j]==1) b++;
				//벽의 개수 카운트
			}
		}
		combi(0, 0, 0);
		
		System.out.println(res);
	}
	
	public static void combi(int cnt, int startx, int starty) {
		if(cnt == 3) {
			bfs();
			return;
		}
		
		for(int j=starty;j<m;j++) {
			if(map[startx][j]==0) {
				select[cnt] = new node(startx, j);
				combi(cnt+1, startx, j+1);
			}
		}
		
		if(startx+1<n) {
			for(int i=startx+1;i<n;i++) {
				for(int j=0;j<m;j++) {
					if(map[i][j]==0) {
						select[cnt] = new node(i, j);
						combi(cnt+1, i, j+1);
					}
				}
			}
		}
	}
	
	public static void bfs() {
		for(node s:select) {
			map[s.x][s.y] = -1;
		}
		
		Queue<node> q = new LinkedList<node>();
		
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
		
		int cnt =0;
		
		for(node v:virus) {
			q.add(new node(v.x, v.y));
			while(!q.isEmpty()) {
				int x = q.peek().x;
				int y = q.peek().y;
				q.poll();
				for(int i=0;i<4;i++) {
					int nowx = x+dx[i];
					int nowy = y+dy[i];
					if(nowx<0||nowy<0||nowx>=n||nowy>=m) continue;
					if(map[nowx][nowy]!=0) continue;
					map[nowx][nowy] = -2;
					cnt++;
                    //바이러스가 퍼질 때 마다 카운트를 해줌으로써 이따가 안전영역 크기를 뺄셈으로 구할 수 있다.
					q.add(new node(nowx, nowy));
				}
			}
		}
		res = Math.max(res, n*m-b-3-virus.size()-cnt);
        //안전영역의 크기 n*m - 입력으로 받은 벽의 개수 - 세운벽 3개 - 바이러스의 개수 - 전염된 영역의 개수
		
        //다시 돌려놓기
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(map[i][j]==-2||map[i][j]==-1) map[i][j]=0; 
			}
		}
	}
}

class node{
	int x,y;

	public node(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
	
}