연구소


백준 [14502] 연구소

문제보기
Alt text

풀이

  • list에 바이러스 위치를 담고 buildWall()를 통해 벽이 3개가 세워지면 safeZone()에서 바이러스를 확산시키고 안전영역 갯수 확인.
  • 주의사항 : queue가 다음 buildWall()에서 비어버린 상태가 아니도록 조심. 즉 queue를 같은 주소로 쓰는지 아닌지 확인.

소스코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int N, M, safezone, ans;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };
	static ArrayList<int[]> list;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		int[][] map = new int[N][M];
		safezone = 0;
		ans = 0;
		list = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
				if (map[i][j] == 2) {
					list.add(new int[] { i, j });
				} else if (map[i][j] == 0)
					safezone++;
			}
		}

		buildWall(0, map);
		System.out.println(ans);
	}

	public static void buildWall(int cnt, int[][] map) {
		if (cnt >= 3) {
			Queue<int[]> queue = new LinkedList<>();
			for (int i = 0; i < list.size(); i++) {
				queue.add(list.get(i));
			}
			safeZone(map, queue);
			return;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0) {
					map[i][j] = 1;
					buildWall(cnt + 1, map);
					map[i][j] = 0;
				}
			}
		}
	}

	public static void safeZone(int[][] map, Queue<int[]> queue) {
		int cnt = safezone - 3;
		boolean[][] visited = new boolean[N][M];

		while (!queue.isEmpty()) {
			int[] q = queue.poll();
			for (int k = 0; k < 4; k++) {
				int x = q[0] + dx[k];
				int y = q[1] + dy[k];

				if (isRange(x, y) && map[x][y] == 0 && !visited[x][y]) {
					visited[x][y] = true;
					cnt--;
					queue.add(new int[] { x, y });
				}
			}
		}
		ans = Math.max(ans, cnt);
	}

	public static boolean isRange(int x, int y) {
		return x >= 0 && y >= 0 && x < N && y < M;
	}
}