백준 | 14502번. 연구소 - DFS & BFS

⬛ 백준 14502번. 연구소 - DFS & BFS

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개 이상이다.

출력

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

---

💚나의 풀이

1) 이중 for()문을 돌면서 기존에 빈칸값 0을 갖는 각각의 i에 대한 j에서 벽을 3개씩 세운 뒤

2) 3개 세울 때마다 BFS()를 호출한 뒤 retrun 하는 식으로 풀었다.

• 이중 map은 (1) 원본 map 과 (2) virus가 뻗어간 map 2개를 사용했다.
• 원본을 갖고 있어야 하므로 DFS 에서 뻗어갈 때, 복귀 시, 다시 기존 값으로 세팅하도록 했고
• virus는 BFS()에서 매번 새롭게 생성하여 2인 바이러스가 뻗어갈 수 있는 한 모두 뻗어가도록 하다가, 그럼에도 남아있는 0의 영역을 cnt로 ++ 처리하여 최종 정적변수인 max값을 갱신시키도록 하였다.
• 결과적으로 DFS()로 벽 3개를 매번 세우고, 3번 세운 상태의 map에서 BFS()로 바이러스가 뻗어가도록 처리한 뒤, 남아있는 0의 영역을 매번 체크하는 방식이다.

package to_1006_1;

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

/*14502번. 연구소 - DFS & BFS 문풀 */
public class Main {
	static int N, M;
	static int[][] map;
	//4방향 
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	static int[][] virusMap;//얘는 BFS 할때마다 갱신될 용도긴 함
	//max
	static int max = Integer.MIN_VALUE;
	
	//DFS -> 벽 3개씩 세우기 
	static void DFS(int wall) {//시작 벽 개수 
		if(wall == 3) {
			//3개가 세워졌을 떄 
			BFS();///호출시킴 2 퍼뜨려야 하니까 
			return;//복귀
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 0) {//0인 지점에서 
					map[i][j] = 1;
					DFS(wall+1);//벽 하나 세우고 깊이 탐색
					//돌아오면 초기화
					map[i][j] = 0;//0처리 
				}
			}
		}
	}
	
	
	//BFS -> 3개씩 세워질 때마다 BFS로 바이러스 퍼뜨리기 
	static void BFS() {
		Queue<int[]> Q = new LinkedList<>();
		virusMap = new int[N][M];//새롭게 2 뻗어가는 애들 만들거고 
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				virusMap[i][j] = map[i][j];//복사시킨 뒤 
				if(virusMap[i][j] == 2) {
					//바이러스 존재하는 애들을 
					Q.offer(new int[] {i, j});
				}
			}
		}
		//1) 3개 세운 상태에서 2의 시작점이 뻗어갈 수 있는 곳까지 다 뻗어간 뒤에 
		while(!Q.isEmpty()) {
			int[] cur = Q.poll();
			
			for(int k=0; k<4; k++) {
				int nx = cur[0] + dx[k];
				int ny = cur[1] + dy[k];
				if(nx <0 || ny <0 || nx>=N || ny>=M )continue;
				
				if(virusMap[nx][ny] == 0) { //닿을 수 있는 0인 지점을 모두 뻗어감 
					//바이러스로 뻗어갈 수 있는 곳까지 뻗어감 
					virusMap[nx][ny] = 2;
					Q.offer(new int[] {nx, ny});
				}
			}
		}
		
		//2) 그럼에도 여전히 0으로 남아있는 영역을 max로 갱신시키면 됨 
		int cnt = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(virusMap[i][j] == 0) {
					//남아있는 0의 영역에 대하여 
					cnt++;
				}
			}
		}
		//max값을 갱신
		max = Math.max(max, cnt);//더 큰 값으로 
		
	}
	
	//실행 메인 
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		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());
			}
		}	
		
		DFS(0);
		System.out.println(max);
	}
}