[BJ] 14502. 연구소

 

www.acmicpc.net/problem/14502

14502번: 연구소

 

✔ 문제 조건

1. 칸에는 빈 칸 (0), 벽 (1), 바이러스 (2)가 올 수 있다.

2. 바이러스는 상하좌우 인접한 빈 칸으로 퍼져나갈 수 있다.

2-1. 바이러스는 벽으로는 퍼져나갈 수 없다.

3. 빈칸에 벽을 세워 바이러스를 막을 수 있다. 무조건 3개의 벽을 세워야 한다.

4. 바이러스가 모두 퍼졌을 때까지 남아있는 빈칸을 안전 영역이라고 한다. 안전 영역의 크기의 최대값을 구해야 한다.

 

✔ 접근 과정

1. 무조건 벽을 3개 세워야 하는데, 벽을 세울 수 있는 모든 경우의 수를 재귀로 다 따져보면 시간 초과가 날 것이라 생각했다.

2. visited 배열을 3차원으로 선언해서 벽을 세울 때 마다 다르게 방문 체크를 할까 했지만 도저히 방법을 모르겠다.

3. 문제 조건을 다시 보니 3 ≤ N, M ≤ 8이다. 즉 연구소의 크기가 크지 않아 빈 칸에 벽을 3개 세울 수 있는 모든 경우의 수를 다 따져보아도 된다. 최악의 경우에도 64 C 3 밖에 되지 않는다.

 

✔ 해결

1. DFS를 돌며 벽 3개를 세운다.

2. 벽을 3개 다 세웠을 때마다 BFS로 바이러스를 퍼뜨린다.

3. 남아있는 안전 영역의 개수를 세고 최대값을 갱신한다.

 

✔ 주의할 점

1. DFS로 벽을 하나씩 세운 후, 다음 DFS를 재귀로 호출하고 나면 세웠던 벽을 없애야 한다.

2. BFS로 바이러스를 퍼뜨릴 때 마다 원본 map 배열에 퍼뜨리지 말고, map을 복사해서 사용해야 한다.

 

 

import java.io.*;
import java.util.*;
// 210326

public class Main_BJ_14502_연구소 {
	static int N, M, max;
	static int[][] map, mapClone;
	
	static class Virus {
		int r, c;

		public Virus(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	
	static void makeWall(int cnt) { // dfs로 벽 세우기
		if(cnt==3) {
			spreadVirus();
			return;
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j]==0) {
					map[i][j] = 1;
					makeWall(cnt+1);
					map[i][j] = 0;
				}
			}
		}
	}
	
	static int[] dr = {-1, 0, 1, 0};
	static int[] dc = {0, -1, 0, 1};
	static void spreadVirus() { // bfs로 퍼뜨리기
		mapCopy();
		
		Queue<Virus> q = new ArrayDeque<Virus>();
		boolean[][] v = new boolean[N][M];
		
		// 1. q에 바이러스 위치 넣기
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(mapClone[i][j]==2) {
					q.offer(new Virus(i, j));
					v[i][j] = true;
				}
			}
		} 
		
		// 2. 퍼뜨리기
		Virus cur = null; 
		int nr, nc;
		while(!q.isEmpty()) {
			cur = q.poll();
			
			for(int d=0; d<4; d++) {
				nr = cur.r + dr[d];
				nc = cur.c + dc[d];
				
				if(nr<0 || nr>=N || nc<0 || nc>=M || v[nr][nc]) continue;
				if(mapClone[nr][nc]==0) {
					mapClone[nr][nc] = 2;
					q.offer(new Virus(nr, nc));
					v[nr][nc] = true;
				}
			}
		}
		
		// 3. 남은 safeZone 세기
		int safeZone = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(mapClone[i][j]==0) ++safeZone;
			}
		}
		
		max = Math.max(max, safeZone);
		
	}
	
	static void mapCopy() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				mapClone[i][j] = map[i][j];
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
//		System.setIn(new FileInputStream("res/input_BJ_14502_연구소.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		max = 0;
		map = new int[N][M];
		mapClone = 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] = stoi(st.nextToken());
			}			
		}
		
		makeWall(0);

		System.out.println(max);
		br.close();
	}
	
	static int stoi(String str) {
		return Integer.parseInt(str);
	}
}