[14502] 연구소

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

---

그나마 역량테스트 기출문제 중에 쉬운편에 속하는 문제인데, 저는 너무 어려워서 https://whereisusb.tistory.com/219 블로그를 참고하여 풀었습니다. 아직 실력이 한참 부족한 것 같습니다............................

처음에 문제를 읽고 어떻게 3개의 벽을 배치할까 생각했는데, 2를 주변으로 BFS를 해서 1과 만나는 부분에 벽을 배치하려고 했습니다. 하지만 3번째 예제를 보면 1이 없는 상황도 있기 때문에, 한참 문제만 보다가 블로그를 참고해서 힌트를 얻었습니다. 문제를 꼼꼼하게 읽는 것이 정말 중요하다고 생각했습니다............ 입력의 범위를 보면 N과 M 둘다 8보다 작기 때문에 매우 작습니다. N과 M이 8로 가장 클 때를 살펴보아도 64개중에 3개의 벽을 뽑는 경우의 수는 64C3으로 계산해보아도 41,664 로 작기 때문에, 완전 탐색(브루트포스)로 벽 3개를 배치했을 때 모든 경우에 안전 영역의 크기를 계산해서 그 중에 최대값을 구하면 되는 문제였습니다. 안전영역을 구하는건 쉬운데, 어떻게 벽3개를 배치하는 모든경우를 고려해야 할지 위의 블로그를 통해 힌트를 얻었습니다.

제가 예전에 정리했던 로또 문제( https://daily-life-of-bsh.tistory.com/58 ) 처럼 벽의개수가 3개가 되었을 때 백트래킹으로 안전영역을 계산하면 되는 문제였습니다. 로또 문제는 1차원 배열에서 백트래킹으로 모든 경우의 수를 출력하는 것이었지만, 이번 문제는 2차원 배열에서 3개의 자리에 1을 넣는 모든 경우의 수를 구하는 것이기 때문에 좀 달랐습니다. 2차원 배열의 백트래킹 하는 방법은 처음 봐서 이 부분을 잘 외워둬야겠습니다.

< 문제 풀이 >

1. 주어진 예제를 입력받고, walling() 함수를 실행합니다. walling(int x, int y, int cnt) 함수는 벽 3개를 세우는 모든 경우의 수를 시행하는 함수인데, 처음 좌표인 (0, 0)부터 시작 합니다. cnt는 벽의 개수를 나타내는데, 3개가 되면 안전영역 구하기 calc_safe() 를 실행합니다. walling(0, 0, 0) 을 실행하게 되면, 2차원 배열에 벽을 나타내는 1이 3개 들어가는 모든 경우를 수행합니다.

2. walling() 함수에 대한 각 설명은 코드에 주석으로 표시했습니다.

3. calc_safe() 함수는 안전영역 safe_area 를 구하는 함수입니다. 이 함수를 부를 때 마다 visited[][]배열을 초기화하고, 벽이 3개 들어간 배열 arr 을 map에 복사하여 안전영역을 구합니다. 처음에는 벽이 3개 세워진 map이 만들어지는데, 여기에서 바이러스 2를 찾아 DFS를 수행하여 바이러스를 퍼뜨리고, 0인 개수를 모두 더하면 safe_area가 구해집니다. 바이러스를 퍼뜨리는 과정은 DFS 말고도 BFS를 사용할 수 있는데, 저는 DFS로 해봤습니다. 그리고 마지막에 구해진 safe_area를 계속 비교해주면서 최대값을 result에 저장해서 출력 합니다.

---

import java.util.Scanner;

// 14502 연구소
public class Main {
	static int N, M, result = -987987987;
	static int [][] map, arr;
	static boolean[][] visited;
	static int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		arr = new int[N][M];
		map = new int[N][M];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		
		walling(0, 0, 0);
		
		System.out.println(result);
	}
	
	public static void walling(int x, int y, int cnt) {
		
		// 벽을 3개 세웠으므로 안전영역을 구하기 위해 calc_safe를 실행한다.
		if(cnt == 3) {
			calc_safe();
			return;
		} else {
			// y의 좌표가 M보다 커지면 다음 행으로 넘어 간다.
			if(y>=M) {
				walling(x+1, 0, cnt);
				return;
			}
			
			// x의 좌표가 N보다 커지면 더이상 탐색할 곳이 없으므로 return
			if(x>=N) return;
			
			// (x, y)가 0이면 벽을 세워준다.
			if(arr[x][y] == 0) {
				arr[x][y] = 1;
				// 벽을 세워주고 y좌표를 1증가시켜 다음 좌표를 탐색. 벽의개수를 나타내는 cnt를 1증가.
				walling(x, y+1, cnt+1);
				// 위에서 하나의 벽을 세워서 재귀를 끝냈으면, 방금 세웠던 벽은 0으로 다시 만들어 주어야 한다.
				arr[x][y] = 0;
			}
			// 세울 벽이 없다면 다음 좌표로 넘어간다.
			walling(x, y+1, cnt);
		}
	}
	
	public static void calc_safe() {
		
		visited = new boolean[N][M];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				map[i][j] = arr[i][j];
			}
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 2) {
					DFS(i, j);
				}
			}
		}
		
		int safe_area = 0;
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 0) safe_area++;
			}
		}
		
		result = Math.max(result, safe_area);
		
	}
	
	public static void DFS(int x, int y) {
		
		visited[x][y] = true;
		
		for(int i=0; i<4; i++) {
			int nx = x+dir[i][0];
			int ny = y+dir[i][1];
			
			if(isInside(nx, ny) && map[nx][ny] == 0 && visited[nx][ny] == false) {
				map[nx][ny] = 2;
				DFS(nx, ny);
			}
		}
		
	}
	
	public static boolean isInside(int x, int y) {
		if(x>=0 && x<N&& y>=0 && y<M) return true;
		else return false;
	}
}