[백준 14502] 연구소 문제 풀이

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

접근

1. 재귀를 이용해서 3개의 벽을 세웁니다.

2. BFS 또는 DFS를 이용하여 바이러스를 퍼트립니다.

3. 안전 영역의 개수를 구합니다.

4. 안전 영역의 최댓값을 구합니다.

 

코드

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

class Virus {
	int r, c;

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

public class Main {
	static int n, m, maxSafeArea;
	static int[][] map, nextMap;

	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	static ArrayList<Virus> viruses = new ArrayList<>();

	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];
		nextMap = 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) {
					viruses.add(new Virus(i, j));
				}
			}
		}

		setWall(0, 0);

		// 결과 출력
		System.out.println(maxSafeArea);
	}

	// 1. 3개의 벽을 세운다.
	static void setWall(int start, int count) {
		if (count == 3) {
			for (int i = 0; i < n; i++) {
				System.arraycopy(map[i], 0, nextMap[i], 0, m);
			}

			for (Virus virus : viruses) {
				spread(virus.r, virus.c);
			}

			maxSafeArea = Math.max(maxSafeArea, getSafeArea());
			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;
				setWall(i + 1, count + 1);
				map[r][c] = 0;
			}
		}
	}

	// 2. 바이러스를 퍼트린다.
	static void spread(int r, int c) {
		for (int dir = 0; dir < 4; dir++) {
			int nr = r + dr[dir];
			int nc = c + dc[dir];
			if ((0 <= nr && nr < n && 0 <= nc && nc < m) && nextMap[nr][nc] == 0) {
				nextMap[nr][nc] = 2;
				spread(nr, nc);
			}
		}
	}

	// 3. 안전 영역의 개수를 구한다.
	static int getSafeArea() {
		int safeArea = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (nextMap[i][j] == 0) {
					safeArea++;
				}
			}
		}
		return safeArea;
	}
}