백준 14502 : 연구소

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

14502번: 연구소

[ 문제풀이 ]

이번에도 간단한 시뮬레이션 문제이다. 0인 공간에 벽을 세우면서 3개를 세웠을 경우 바이러스를 퍼트려 안전 공간의 개수를 카운트해 주면 쉽게 해결할 수 있다.

​벽을 3개 세우는 경우의 수를 구하는 것은 백트래킹 기법을 통해 구하면 될 것이다.

​나는 처음에 Virus라는 클래스를 구현하여 바이러스들을 관리해줬는데 매번 새로운 바이러스 객체를 생성해주는 것은 메모리에 부담이 크다.

어차피 바이러스들은 멤버 변수로 y, x만 가지기 때문에 객체가 아닌 배열로 접근한다면 메모리를 많이 줄일 수 있을 것이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	static int N, M, answer;
	static int[][] map, temp;

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

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

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

		makeBrick(0, 0, 0);

		bw.write(answer + "\n");
		bw.flush();bw.close();br.close();
	}
	
	public static void makeBrick(int y, int x, int brick_Cnt) {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) {
				//중복 조합을 방지하기 위해 이전 다음 칸부터 탐색
				if (i == 0 && j == 0) {
					i = y; j = x;
				}

				//빈 공간이라면
				if (map[i][j] == 0) {
					map[i][j] = 1; //벽 설치
					
					//설치한 벽이 3개라면 바이러스를 퍼트림
					if (brick_Cnt == 2) {
						spreadVirus();
						answer = Math.max(answer, getSafeArea());
					} else {
						makeBrick(y, x + 1, brick_Cnt + 1);
					}
					
					map[i][j] = 0; //벽 해제
				}
			}
		}
	}

	public static void copyMap() {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) {
				temp[i][j] = map[i][j];
			}
		}
	}

	public static void spreadVirus() {
		copyMap();

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

	public static void dfs(int y, int x) {
		for (int d = 0; d < 4; ++d) {
			int ny = y + dir[d][0];
			int nx = x + dir[d][1];

			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (temp[ny][nx] != 0) continue;

			temp[ny][nx] = 2;
			dfs(ny, nx);
		}
	}

	public static int getSafeArea() {
		int count = 0;

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

		return count;
	}
}