/ BOJ

BOJ_14502_연구소_JAVA

문제 : 연구소

링크 : BOJ_14502_연구소

접근 방식

바이러스가 퍼지지 않도록 벽을 세워야 하는 문제이다.

나는 이 문제를 조합과 BFS를 통해서 시뮬레이션 문제처럼 접근했다.

다만 기존의 조합은 6개 중에 3개 뽑기 등과 같이 1차원으로 구하는 것이 한계라고 생각했다. 따라 2차원 배열에서 특정한 좌표를 뽑을 수 있게, 조합 함수를 수정하였다.

그리고, 각 조합이 선택된 경우의 수에 따라서 각각 BFS를 수행해주면서, 한 번 수행할 때마다 남아있는 감염되지 않은 공간 구하여 그 최댓값을 출력하도록 했다.

소스 코드

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

public class BOJ_14502_연구소 {

	static int N, M, arr[][], temp[][];
	static int numbers[][];
	static int max;
	static boolean[][] visited;
	static int dir[][] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
	static ArrayList<int[]> virus;
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new int[N][M];

		numbers = new int[3][2];

		virus = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if(arr[i][j] == 2) {
					virus.add(new int[] {i,j});
				}
			}
		}

		comb(0, 0);

		System.out.println(max);

	}

	static void comb(int start, int cnt) {

		if (cnt == 3) {

			temp = new int[N][M];
			for (int i = 0; i < N; i++) {
				temp[i] = arr[i].clone();
			}

			for (int i = 0; i < 3; i++) {
				if(temp[numbers[i][0]][numbers[i][1]] == 0) {
					temp[numbers[i][0]][numbers[i][1]] = 1;
				}else {
					return;
				}
			}
			Queue<int[]> queue = new ArrayDeque<>();
			for (int[] v : virus) {			
				queue.offer(v);
			}
			while (!queue.isEmpty()) {

				int[] node = queue.poll();
				for (int d = 0; d < 4; d++) {
					int dx = node[0] + dir[d][0];
					int dy = node[1] + dir[d][1];

					if (dx >= 0 && dx < N && dy >= 0 && dy < M && temp[dx][dy] == 0) {
						temp[dx][dy] = 2;
						queue.offer(new int[] { dx, dy });
					}
				}
			}

			int count = 0;
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(temp[i][j] == 0) {
						count++;
					}
				}
			}

			max = Math.max(max, count);

			return;
		}

		for (int i = start; i < N * M; i++) {

			int x = i / M;
			int y = i % M;

			numbers[cnt] = new int[] { x, y };
			comb(i + 1, cnt + 1);
		}

	}

}

2차원 배열에서 좌표를 고르는 조합에 대한 부분이 포인트였던 것 같다.