[Baekjoon Online Judge] 14502 - 연구소 / Java

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

14502번: 연구소

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

public class Main {

	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	static int N, M, maxSafyArea = 0;
	static int[][] map, spreadMap;
	static ArrayList<Pos> virusList = new ArrayList<>();

	static class Pos {
		int r, c;

		public Pos(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer 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) {
					virusList.add(new Pos(i, j));
				}
			}
		}

		combination(0, 0);
		System.out.println(maxSafyArea);
	}

	private static void combination(int cnt, int start) {
		// 벽 세우기

		if (cnt == 3) {
			// 바이러스 뿌리고
			spreadVirus();
            
			// maxSafyArea 구하기
			maxSafyArea = Math.max(maxSafyArea, getMaxSafyArea());
			return;
		}

		for (int i = start; i < N * M; i++) {
			int r = i / M; // 행
			int c = i % M; // 열

			if (map[r][c] == 0) {
				map[r][c] = 1;
				combination(cnt + 1, i + 1);
				map[r][c] = 0;
			}
		}
	}

	private static void spreadVirus() {
		arrayCopy();

		Queue<Pos> q = new LinkedList<>();

		for (Pos pos : virusList) {
			q.offer(pos);
		}

		while (!q.isEmpty()) {
			Pos p = q.poll();

			for (int dir = 0; dir < 4; dir++) {
				int nr = p.r + dr[dir];
				int nc = p.c + dc[dir];

				//경계 내에 있고 빈칸 이라면
				if (nr >= 0 && nr < N && nc >= 0 && nc < M && spreadMap[nr][nc] == 0) {
					spreadMap[nr][nc] = 2;
					q.offer(new Pos(nr, nc));
				}
			}
		}
	}

	private static void arrayCopy() {
		spreadMap = new int[N][];
		for (int i = 0; i < N; i++) {
			spreadMap[i] = map[i].clone();
		}
	}

	private static int getMaxSafyArea() {
		int safeArea = 0;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (spreadMap[i][j] == 0) {
					safeArea++;
				}
			}
		}
		return safeArea;
	}
}