[Java] 백준 / 연구소 / 14502

[Java] 백준 / 연구소 / 14502

문제

연구소 문제 링크

접근 방식

1. 빈 칸중 벽을 3개 세울 경우의 수를 조합으로 모두 구하여 세 위치를 벽으로 바꾼다
2. 벽을 선택한 지도에서 바이러스를 찾아 해당 좌표를 bfs의 큐에 넣어 사방탐색한다
3. 빈 칸이 아닌 곳까지 모두 탐색한 후 나머지 빈 칸을 세어 최소값을 저장한다

코드

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

public class Main_14502 {

	static int N,M;
	static int mat[][];
	static List<int[]> blank;
	static int numbers[];
	static List<int[]> virus;
	static int[][] deltas = {{0,1},{1,0},{0,-1},{-1,0}};
	static int maxSafezone;
	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());
		
		mat = new int[N][M];
		
		blank = new ArrayList<>();
		virus = new ArrayList<>();
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++) {
				mat[i][j] = Integer.parseInt(st.nextToken());
				if(mat[i][j] == 0) {
					blank.add(new int[] {i,j});
				}
				if(mat[i][j] == 2) {
					virus.add(new int[] {i,j});
				}
			}
		}
		
		numbers = new int[3];
		maxSafezone = 0;
		// =================== 솔루션 =======================
		
		combination(0,0);
		
		System.out.println(maxSafezone);
		
	}

	
	
	public static void combination(int cnt, int start) {
		
		if(cnt == 3) { // 벽 선택 완료
			int temp[][] = new int[N][M];
			
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					temp[i][j] = mat[i][j];
				}
			}
			
			for(int i=0;i<3;i++) {
				int data[] = blank.get(numbers[i]);
				temp[data[0]][data[1]] = 1;
			}
			
			boolean[][] visited = new boolean[N][M];
			bfs(temp, visited);
			
			
			return;
		}
		
		for(int i=start; i<blank.size();i++) {
			numbers[cnt] = i;
			combination(cnt+1,i+1);
		}
	}
	
	public static void bfs(int[][] temp, boolean[][] visited) {
		
		Queue<int[]> que = new LinkedList<>();
		
		for(int i=0;i<virus.size();i++) {
			int[] virusData = virus.get(i);
			que.add(virusData);
			visited[virusData[0]][virusData[1]] = true;
		}
		
		while(!que.isEmpty()) {
			int[] virusData = que.poll();
			
			for(int i=0;i<4;i++) {
				int nextR = virusData[0] + deltas[i][0];
				int nextC = virusData[1] + deltas[i][1];
				
				// 다음 탐색할 칸이 범위를 벗어났거나 이미 방문했거나 빈칸이 아니면 넘어간다
				if(nextR < 0 || nextR >= N || nextC < 0 || nextC >= M || visited[nextR][nextC] || temp[nextR][nextC] != 0 ) continue;
				
				temp[nextR][nextC] = 2;
				visited[nextR][nextC] = true;
				que.add(new int[] {nextR,nextC});
			}
		}
		
		int cnt = 0;
				
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(temp[i][j] == 0) {
					cnt++;
				}
			}
		}
				
		maxSafezone = Math.max(cnt, maxSafezone);
		
		
	}
}