[백준] 14502: 연구소 (Java)

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

14502번: 연구소

 

 

package 백준;

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

public class Main_14502 {
	static class Point {
		int y, x;

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

	}

	static int originMap[][];
	static int copyMap[][];
	static int N, M, resultMax = Integer.MIN_VALUE;
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };
	static ArrayList<Point> virus = new ArrayList<>();

	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());
		originMap = new int[N][M];

		// 입력값 넣기
		for (int y = 0; y < N; y++) {
			st = new StringTokenizer(br.readLine());
			for (int x = 0; x < M; x++) {
				int tmp = Integer.parseInt(st.nextToken());
				originMap[y][x] = tmp;
				if (tmp == 2) { // 바이러스 좌표를 리스트에 담아둠
					virus.add(new Point(y, x));
				}
			}
		}

		// 벽을 3개 세우는 경우의 수(조합)
		combination(0, 0, 0);
		System.out.println(resultMax);

	}

	private static void combination(int y, int x, int cnt) {
		// 기능: 벽 3개를 뽑음
		if (cnt == 3) {
			copy();// 맵 복사해서 사용 기존의 맵은 변화X
			for (int i = 0; i < virus.size(); i++) {

				spread(virus.get(i).y, virus.get(i).x);// 바이러스를 퍼뜨림
			}
			servive(); // 살아 남은 지역 cnt
			return;
		}
		for (int row = 0; row < N; row++) {
			for (int col = 0; col < M; col++) {
				if (originMap[row][col] == 0) { // 벽이 아닌 지역 발견 시
					originMap[row][col] = 1; // 벽을 세워봄
					combination(row, col, cnt + 1);
					originMap[row][col] = 0; // 다시 원래대로 복귀
				}
			}
		}

	} // combi-end

	private static void copy() {
		// 기능: 바이러스를 퍼뜨리기 위해 맵을 잠시 카피해놓음
		copyMap = new int[N][M];
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				copyMap[y][x] = originMap[y][x];
			}
		}

	}

	private static void servive() {
		// 기능: 바이러스를 퍼트린 뒤 살아 남은 연구소의 개수 카운트
		// 카운트 이후 최댓값 갱신
		int cnt = 0;
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if (copyMap[y][x] == 0) {
					cnt++;
				}
			}
		} // 연구소 개수 카운트 끝

		if (resultMax < cnt) {
			resultMax = cnt;
		}

	}

	private static void spread(int y, int x) {
		// 기능 : 2(바이러스)를 상하좌우로 퍼뜨림
		Queue<Point> que = new ArrayDeque<>();
		que.add(new Point(y, x));

		while (!que.isEmpty()) {
			Point node = que.poll();

			for (int i = 0; i < 4; i++) {
				int nx = node.x + dx[i];
				int ny = node.y + dy[i];

				if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
					if (copyMap[ny][nx] == 0) {
						copyMap[ny][nx] = 2;
						que.add(new Point(ny, nx));
					}
				}

			}
		}

	}
}