[JAVA] 백준 14502번 : 연구소 (삼성 SW 역량 테스트 기출 문제)

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

14502번: 연구소

문제

벽 3개 세우는 경우를 완전 탐색하고 벽이 3개 세워진 경우에 바이러스를 퍼트려서 최대 안전 구역 크기를 구해주는 문제이다.

생각보다 쉽게 풀려서 놀랐다. DFS + BFS 문제

 

해결 방안

1. 메인에서 지도값 입력받을 때 바이러스의 좌표를 저장할 수 있는 자료구조(여기서는 ArrayList 사용함)를 사용해준다. (나중에 BFS 탐색에서 Queue에 넣어줄 값)

2. DFS 탐색을 이용하여 벽이 3개가 추가된 경우를 완전탐색한다.(벽이 3개가 추가된 지도가 만들어진다.)

3. DFS 탐색의 기저 사례에 벽이 3개가 추가된 경우로 설정해주고 해당 경우마다 바이러스를 BFS 탐색을 이용하여 퍼트려준다.
3.1. 이 때, 해당 지도를 copy한 지도를 만들어준다. (기존 지도는 DFS를 통해 계속 사용해야하므로)
3.2. copy된 지도에 BFS 탐색을 이용하여 바이러스를 퍼트려준다.
3.3. 바이러스가 퍼트려진 copy된 지도의 안전 구역 크기를 구해준다.
3.4. 기존에 누적된 max 안전 구역 크기와 비교하여 새로운 max 안전 크기 구역을 구해준다.

4. 바이러스가 퍼지는 부분을 BFS를 이용하여 구해주었다. (3.2 부분)
4.1. 3.2 부분에서 바이러스를 퍼트릴때 1.에서 저장한 바이러스 좌표를 Queue에 넣어주고 visited를 true로 만들어준다.
4.2. 바이러스 좌표의 상하좌우 부분의 경우 범위가 지도 범위를 넘어가는지 확인해주고 방문 안했으며 빈 칸인 경우 바이러스를 확진 시켜준다.
4.3. BFS 탐색이 끝나면 해당 map을 반환해준다.
4.4. 끝나면 3.2 과정이 끝나 3.3 과정이 시작한다.

 

코드

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

// 연구소
// 바이러스 확산을 막기 위해서 연구소에 벽을 세우려고함
// NxM 직사각형의 연구소
// 바이러스는 인접한 빈칸(상하좌우)으로 모두 퍼져나감
// 새로 세울 수 있는 벽의 갯수는 3개
// 0:빈칸  1:벽  2:바이러스
// 안전 영역(바이러스, 벽 제외한 부분) 크기의 최댓값을 구하는 프로그램 작성
public class Main {

	static int N; // 세로 (3~8)
	static int M; // 가로 (3~8)
	static int[][] maps; // 지도
	static boolean[][] visited;
	
	// 바이러스 움직임 (상하좌우)
	static int[] dx = {-1, 1, 0, 0}; // 세로
	static int[] dy = {0, 0, -1, 1}; // 가로
	
	static List<int[]> virusLocation = new ArrayList<>(); // 바이러스 좌표
	
	static int max_safe = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str;
		str = br.readLine();
		N = Integer.parseInt(str.split(" ")[0]);
		M = Integer.parseInt(str.split(" ")[1]);
		
		maps = new int[N][M];
		visited = new boolean[N][M];
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			for(int j=0; j<M; j++) {
				maps[i][j] = Integer.parseInt(st.nextToken());
				
				if(maps[i][j] == 2) {
					virusLocation.add(new int[] {i, j});
				}
			}
		}
		//====== 입력 끝 ========
		
		// 완전 탐색으로 3개의 벽 세우고 바이러스 퍼졌을 때 안전지역이 최대값을 찾는 프로그램
		dfs(0);
		
		
		System.out.println(max_safe);

	}
	
	public static int[][] copyMap() {
		int[][] copy_maps = new int[N][M];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				copy_maps[i][j] = maps[i][j];
			}
		}
		
		return copy_maps;
	}
	
	//바이러스 퍼지는 것을 bfs로 구현
	public static int[][] bfs(int[][] copy_maps, boolean[][] visited) {
		
		Queue<int[]> q = new LinkedList<>();
		
		// 처음 바이러스좌표를 Queue에 넣어줌
		int[] loc = new int[2];
		for(int i=0; i<virusLocation.size(); i++) {
			loc = virusLocation.get(i);
			q.offer(new int[] {loc[0], loc[1]});
			visited[loc[0]][loc[1]] = true;
		}
		
		// 현재 바이러스 위치
		int cx, cy;
		int nx, ny;
		int[] tempLoc;
		while(!q.isEmpty()) {
			tempLoc = q.poll();
			cx = tempLoc[0];
			cy = tempLoc[1];
			
			// 상하좌우 바이러스 퍼트림
			for(int i=0; i<4; i++) {
				nx = dx[i] + cx;
				ny = dy[i] + cy;

				// 범위 넘어가는지 확인
				if(nx<0 || nx>=N || ny<0|| ny>=M) continue;
				
				// 방문 안했고 빈 칸 인지 확인해서 바이러스확진
				if(!visited[nx][ny]) {
					if(copy_maps[nx][ny] == 0) {
						visited[nx][ny] = true;
						copy_maps[nx][ny] = 2;
						q.offer(new int[] {nx, ny});
					}
				}
			}
		}
		
		return copy_maps;
	}
	
	public static void dfs(int cnt) {
		// 벽의 갯수가 3개가 됬을 때
		if(cnt == 3) {
			
			int[][] copy_maps = new int[N][M];
			
			// copy map
			copy_maps = copyMap();
			
			// 바이러스 다 퍼트리고
			boolean[][] visited = new boolean[N][M];
			copy_maps = bfs(copy_maps, visited);
			
			int safe = 0;
			// 안전 지역 갯수 구하고(빈 칸의 갯수)
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					if(copy_maps[i][j] == 0)
						safe++;
				}
			}
			
			// 안전지역 최댓값 구함
			max_safe = Math.max(max_safe, safe);
		}
		else {
			
			// 벽의 갯수 dfs 탐색으로 늘려줌
			for(int i=0; i<maps.length; i++) {
				for(int j=0; j<maps[i].length; j++) {
					// 벽이나 바이러스일 경우 
					if(maps[i][j] == 1 || maps[i][j] == 2) continue;
					// 빈 칸 인 경우
					else {
						// 방문하지 않은 경우
						if(!visited[i][j]) {
							// 빈칸에 벽을 세워줌
							visited[i][j] = true;
							maps[i][j] = 1;
							dfs(cnt+1);
							maps[i][j] = 0;
							visited[i][j] = false;
						}
					}
				}
			}
		}
	}

}