[백준] 14502번 : 연구소

문제

14502번: 연구소

 

접근 방식

최대 8*8 배열이라 백트래킹 + BFS로 무식하게 풀 수 있는 문제다.

 

벽을 3개 이하로 세우는 것이 아니고 무조건 3개를 다 세워야하기 때문에

벽을 3개 추가했을 때마다 BFS를 진행해주면 된다.

 

BFS는 바이러스가 있는 위치를 모두 큐에 넣어준 후에

0인 부분만 탐색을 진행하면서 카운트를 해주고

n * m에서 카운트를 빼주면 바이러스가 퍼지지 않은 지역의 넓이를 알 수 있다.

 

풀이

public class Main {

	static int n, m, max = 0, total;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int[][] map;
	static boolean[][] isVisited;
	static Queue<Pair> q = new ArrayDeque<>();

	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());
		total = n * m;

		map = new int[n][m];
		isVisited = new boolean[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());
			}
		}

		solve(0);

		System.out.println(max);
	}

	static void solve(int wall) {
		if (wall == 3) {
			bfs();
			return;
		}

		for (int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if (map[i][j] != 0) continue;
				map[i][j] = 1;
				solve(wall + 1);
				map[i][j] = 0;
			}
		}
	}

	static void bfs() {
		int virusAndWalls = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				int cur = map[i][j];
				if (cur == 1) {
					virusAndWalls++;
					continue;
				}

				if (cur == 2) {
					isVisited[i][j] = true;
					virusAndWalls++;
					q.offer(new Pair(i, j));
				}
			}
		}

		while (!q.isEmpty()) {
			Pair cur = q.poll();

			for (int dir = 0; dir < 4; dir++) {
				int x = cur.x + dx[dir];
				int y = cur.y + dy[dir];

				if(x < 0 || x >= n || y < 0 || y >= m) continue;
				if(isVisited[x][y] || map[x][y] != 0) continue;

				isVisited[x][y] = true;
				virusAndWalls++;
				q.offer(new Pair(x, y));
			}
		}

		for (int i = 0; i < n; i++) {
			Arrays.fill(isVisited[i], false);
		}

		max = Math.max(max, total - virusAndWalls);
	}

	static class Pair {
		int x, y;

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