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

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

14502번: 연구소

 

풀이

0. 문제 해석

바이러스가 퍼지는 범위를 DFS나 BFS로 구현하여, 최종적으로 변하지 않은 안전 영역을 체크해야 하는 문제이다.

단, 벽이 존재하면 그 벽으로는 퍼져나갈 수 없으며, 벽을 무조건 빈칸에 3개 세워야 한다. 

 

1. 전체 탐색을 통해 임의의 빈칸에 벽을 3개 세우는 모든 경우의 수를 구한다.
2. 벽이 3개 세워 졌을 때, 복사본 배열을 하나 생성하여 그 배열에서 DFS를 진행한다.
3. 모든 경우의 수에서 가장 안전 영역이 큰 경우를 구한다.

 

 

1. 연구소 입력, 벽 만들기

최초의 연구소를 배열에 저장해주고

전체 탐색을 시작하여 빈칸이면 벽을 만들고, 벽을 2개 더 만드는 block 메서드를 호출한다.

 

2. 만든 벽이 3개일 때 탐색 진행

다시 전체탐색을 시작하여 빈칸일 경우 벽을 생성하고 만든 벽이 3개가 되었을 때,

그 배열의 복사본을 생성하여 DFS 탐색을 시작하고, 영역을 체크한다.

 

3. DFS

배열의 복사본을 생성해주고

DFS를 시작하여 바이러스 감염을 확인한다.

DFS가 종료되면 빈칸의 개수를 확인하여 최댓값을 갱신한다.

 

4. 전체 코드

// [백준] 14502. 연구소 (Java)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static StringTokenizer st;
	static int n; // 세로 크기
	static int m; // 가로 크기
	static int max; // 최대 영역
	static int[][] arr; // 원본 배열
	static int[][] tmpArr; // 복사 배열
	
	// 상하좌우
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new int[n][m];
		tmpArr = new int[n][m];
		
		// 연구소 입력
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < m; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 벽 만들기
		for(int i = 0; i < n; i++) {	
			for(int j = 0; j < m; j++) {
				// 빈 칸일때 벽 만들기
				if(arr[i][j] == 0) {
					arr[i][j] = 1;
					block(1);
					arr[i][j] = 0;			
				}
			}
		}	
		
		System.out.println(max);
	}
	
	public static void createTmp() {
		for(int i = 0; i < n; i++) {	
			for(int j = 0; j < m; j++) {
				tmpArr[i][j] = arr[i][j];
			}
		}
	}
	
	public static void block(int count) {	
		// 벽 3개 만들어 졌을 때
		if(count == 3) {
			createTmp(); // 복사본 생성
			dfs(); // 복사본으로 dfs
			countCheck(); // 복사본 영역 체크
			return;
		}
		
		for(int i = 0; i < n; i++) {	
			for(int j = 0; j < m; j++) {		
				// 빈 칸일때 벽 만들기
				if(arr[i][j] == 0) {
					arr[i][j] = 1;
					block(count + 1);
					arr[i][j] = 0;
				}
			}
		}
	}
	
	public static void dfs() {
		for(int i = 0; i < n; i++) {	
			for(int j = 0; j < m; j++) {
				// 바이러스 일 때만 탐색 시작
				if(tmpArr[i][j] == 2) {
					solve(i,j);
				}
			}
		}
	}
	
	public static void solve(int x, int y) {
		tmpArr[x][y] = 2;
		
		for(int i = 0; i < 4; i++) {
			int nextX = x + dx[i];
			int nextY = y + dy[i];
			// 범위 체크
			if(nextX >= 0 && nextY >= 0 && nextX < n && nextY < m) {
				// 바이러스면 감염 시킴
				if(tmpArr[nextX][nextY] == 0) {
					solve(nextX,nextY);
				}
			}
		}
	}
	
	// 안전 영역 카운트
	public static void countCheck() {
		int count = 0;
		for(int i = 0; i < n; i++) {	
			for(int j = 0; j < m; j++) {
				// 빈 칸 갯수
				if(tmpArr[i][j] == 0) {
					count++;
				}
			}
		}
		max = Math.max(max, count);
	}
}