[BOJ-Gold4] 14502번 연구소

💡 풀이

✔️ 조합 + BFS

• 조합 알고리즘으로 빈칸 중 벽 세울 곳 3군데 구하기
• 빈칸 3곳을 골랐으면 bfs 실행
• 나중에 arr 원상복구 시키기 위해 바이러스 감염된 곳은 따로 좌표 보관(newVirus)
• 빈칸 수 count
• 바이러스 새롭게 감염된 곳 다시 빈칸으로 복구

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 {
	static int n, m;
	static int[][] arr;
	static Queue<int[]> q = new LinkedList<>();
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static int result = 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());
		arr = new int[n][m];
		for(int i = 0; i<n; i++){
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j<m; j++){
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		combination(0, 0);
		System.out.println(result);
	}

	public static void combination(int start, int depth){
		// 조합 알고리즘으로 빈칸 중에 3곳 벽으로 처리하고 bfs 실행
		if (depth == 3){
			result = Math.max(result, bfs());
			return;
		}

		for(int i = start; i<n*m; i++){
			int x = i / m;
			int y = i % m;

			if (arr[x][y] != 0) continue;

			arr[x][y] = 1;
			combination(i+1, depth+1);
			arr[x][y] = 0;
		}
	}

	public static int bfs(){
		int cnt = 0;
		List<int[]> newVirus = new ArrayList<>(); // 바이러스 감염된 좌표 저장 -> 원상복구때 필요
		// bfs 실행
		for(int i = 0; i<n; i++){
			for(int j = 0; j<m; j++){
				if (arr[i][j] == 2){
					q.add(new int[]{i, j});
				}
			}
		}

		while(!q.isEmpty()){
			int[] curr = q.poll();
			for(int i = 0; i<4; i++){
				int nx = curr[0] + dx[i];
				int ny = curr[1] + dy[i];

				if (nx >= 0 && nx < n && ny >= 0 && ny < m){
					if (arr[nx][ny] == 0){
						arr[nx][ny] = 2;
						q.add(new int[]{nx, ny});
						newVirus.add(new int[]{nx, ny});
					}
				}
			}
		}

		// 빈칸 count
		for(int i = 0; i<n; i++){
			for(int j = 0; j<m; j++){
				if (arr[i][j] == 0){
					cnt++;
				}
			}
		}
		// 바이러스 감염된 곳 다시 빈칸으로 원상복구
		for(int[] v : newVirus){
			arr[v[0]][v[1]] = 0;
		}
		return cnt;
	}
}