[JAVA] BOJ(백준) - 연구소 - 14502

문제내용

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

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

---

문제 접근 방법

벽을 3개 세우고 빈공간에 바이러스가 퍼진뒤 남아있는 빈공간을 출력하는 문제다.

문제의 의미를 하나하나 생각해보자.

 

벽을 3개 세운다

-> 주어진 2차원 배열에서 어딘가에 0으로 입력된 값 3개에 대해 1로 바꾼다.

-> 0을 1로 바꿀수 있는 모든 경우의 수에 대해 생각해본다. ( 조합 )

-> 백트래킹 사용.

 

벽을 3개 세웠을때 바이러스가 퍼지고 남은 빈공간을 출력한다.

-> 2가 입력된 곳부터 시작하여 상하좌우를 탐색한다.

-> 탐색된 자리가 0일 경우 2로 바꿔준다.

-> 탐색이 끝났으면 현재 2차원 배열에 남은 0의 개수를 세주고 출력한다.

-> BFS or DFS 사용.

 

참고

-> 방문배열은 필요없다.

-> 어차피 2차원 배열을 돌면서 0인곳, 0이 아닌곳을 기준으로 탐색하기 때문에 중복탐색을 하지 않는다.

-> 2차원 배열을 복사할때 clone() 메서드는 사용하면 안된다.

-> clone() 사용시 원본배열의 주소값을 복사하기 때문에 복사한을 작업할때 원본 배열도 같이 작업이 되기 때문이다.

 

위의 생각을 갖고 문제를 풀면된다.

한마디로 벽을 세울수 있는 모든 경우의 수마다 바이러스를 퍼뜨려보고 빈공간이 가장 많이 남는 경우를 택하면된다.

아래 코드를 보고 생각해보자.

 

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int answer = Integer.MIN_VALUE;//정답
	static int n, m;//세로,가로
	static int[] x = {-1, 1, 0, 0};//상하
	static int[] y = {0, 0, -1, 1};//좌우
	static class Node14502 {//인덱스 클래스
		int x;//세로 idx
		int y;//가로 idx
		public Node14502(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	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());
		int[][] map = 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());
			}
		}
		
		//백트래킹으로 벽을 세울수 있는 모든 경우의수를 탐색.
		backTracking(0,map);
		
		System.out.println(answer);
	}
	
	//depth:벽의 개수,    map:벽을 세웠을때의 맵 
	public static void backTracking(int depth, int[][] map) {
		//종료조건, 벽3개 다세웠을때 바이러스 퍼뜨려 보기
		if(depth==3) {
			//bfs쓸 map을 복사
			int[][] subMap = new int[n][m];
			for(int i=0; i<n; i++) {
				for(int j=0; j<m; j++) subMap[i][j] = map[i][j];
			}
		
			BFS(subMap);//바이러스 퍼뜨려 보기
			return;
		}
		
		//각 요소값을 모두 탐색하면서 0인자리를 1로 갱신(벽을 세움)
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				//빈공간 아니면 건너뜀
				if(map[i][j]!=0) continue;
				
				map[i][j] = 1;//벽세우기
				backTracking(depth+1, map);//다음 벽세우러 ㄱㄱ
				map[i][j] = 0;//되돌리기

			}
		}
	}
	
	//subMap:벽을 3개 세우고난뒤 map
	public static void BFS(int[][] subMap) {
		Queue<Node14502> q  = new LinkedList<Node14502>();
		int safeCnt = 0; //안전공간 개수
		int virusCnt = 0; //바이러스있는 공간 개수
		
		//바이러스의 초기시작 인덱스 삽입
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(subMap[i][j]==2) q.add(new Node14502(i, j));
				else if(subMap[i][j]==0) safeCnt++;
			}
		}
		
		//q빌때까지 바이러스 퍼뜨리기
		while(!q.isEmpty()) {
			Node14502 curN = q.poll();
			int curX = curN.x;//현재인덱스(세로)
			int curY = curN.y;//현제인덱스(가로)
			
			//현재 인덱스로 부터 상하좌우 탐색
			for(int i=0; i<4; i++) {
				int nextX = curX + x[i];//다음인덱스(세로)
				int nextY = curY + y[i];//다음인덱스(가로)
				
				if(nextX>=0 && nextY>=0 && nextX<n && nextY<m) {//배열 내의 범위면서
					if(subMap[nextX][nextY]==0) {//빈공간일때 바이러스 퍼뜨리기
						subMap[nextX][nextY] = 2;
						virusCnt++;//퍼진 바이러스 개수 증가
						q.add(new Node14502(nextX, nextY));
					}
				}
			}
		}
		
		//벽 3개 세운 경우마다 "초기안전공간 - 바이러스퍼진공간" 으로
		//안전공간이 최대는 경우를 출력하도록 answer 갱신
		answer = Math.max(answer, safeCnt-virusCnt);
	}
}

---

마치며

풀고나면 쉬운 문제지만 풀기위해 시간좀 썼던 문제이다. 시간을 잡아먹은 부분은 BFS한번으로 풀기 위해 벽3개를 세울수 있는 조건에 대해 생각하다가 시간을 잡아먹었고 backtracking을 통한 조합을 떠올리기 까지 오래 걸렸다.