[백준] 14502 연구소 - JAVA

문제

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

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

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

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다.

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

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

14502번: 연구소

 

접근 방법

이 문제는 벽을 세울 곳을 찾는 것과 바이러스가 퍼져나가는 공간을 계산하는 것 이 두 가지를 어떻게 구현하는냐에 관한 문제라고 생각했습니다. 벽을 세울 곳을 찾을 때는 모든 경우를 다 살펴봐야 하니깐 백트래킹으로 접근하였고, 바이러스가 퍼져나가는 공간을 구하는 것은 BFS로 접근하여 풀었습니다.

 

- 벽을 세울 곳을 찾는 코드

public static void selectThree(int depth, int x, int y) {
		if(depth == 3) {
			for(int i=0; i<3; i++) { 
				map[wall[i].x][wall[i].y] = 1;	// 선택한 칸에 벽을 세움 
			}
			int safety = n*m - wallCount - solution(map);	//안전영역 계산
			answer = Math.max(safety, answer);
			for(int i=0; i<3; i++) {
				map[wall[i].x][wall[i].y] = 0;	// 선택한 칸에서 벽을 지움
			}
			return;
		}
		
        	
		for(int i=0; i<n; i++) {	// 벽을 세울 수 있는 칸 선택
			for(int j=0; j<m; j++) {
				if(map[i][j] == 0 && !check[i][j]) {
					check[i][j] = true;
					wall[depth] = new node(i, j);
					selectThree(depth+1, i, j);
					check[i][j] = false;
				}
			}
		}
	}

 

- 바이러스가 퍼져 나가는 공간 계산 코드

public static int solution(int[][] modMap) {
		int count = 0;
		boolean[][] walls = new boolean[n][m];
		Queue<node> queue = new LinkedList<>();
		for(int i=0; i<virus.size(); i++) {		// 바이러스가 있는 칸을 queue에 add
			queue.add(virus.get(i));
			walls[virus.get(i).x][virus.get(i).y] = true;
			count++;
		}
		
		while(!queue.isEmpty()) {
			node cur = queue.remove();
			
			for(int i=0; i<4; i++) {	// 상하좌우로 이동하면서 퍼져 나갈 수 있는지 확인
				int nextX = cur.x + dir1[i];
				int nextY = cur.y + dir2[i];
				
				if(nextX>=0 && nextY>=0 && nextX<n && nextY<m) {
					if(modMap[nextX][nextY] == 0 && !walls[nextX][nextY]) {
						walls[nextX][nextY] = true;
						count++;
						queue.add(new node(nextX, nextY));
					}
				}
			}
		}
		return count;
	}

 

전체 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int answer = 0, wallCount = 3;
	static int n, m;
	static int[][] map;
	static boolean[][] check;
	static ArrayList<node> virus = new ArrayList<>();
	static node[] wall = new node[3];
	
	static int[] dir1 = {0, 1, 0, -1};
	static int[] dir2 = {1, 0, -1, 0};
	
	static class node{
		int x, y;
		public node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static void selectThree(int depth, int x, int y) {
		if(depth == 3) {
			for(int i=0; i<3; i++) {
				map[wall[i].x][wall[i].y] = 1;
			}
			int safety = n*m - wallCount - solution(map);
			answer = Math.max(safety, answer);
			for(int i=0; i<3; i++) {
				map[wall[i].x][wall[i].y] = 0;
			}
			return;
		}
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(map[i][j] == 0 && !check[i][j]) {
					check[i][j] = true;
					wall[depth] = new node(i, j);
					selectThree(depth+1, i, j);
					check[i][j] = false;
				}
			}
		}
	}
	
	public static int solution(int[][] modMap) {
		int count = 0;
		boolean[][] walls = new boolean[n][m];
		Queue<node> queue = new LinkedList<>();
		for(int i=0; i<virus.size(); i++) {
			queue.add(virus.get(i));
			walls[virus.get(i).x][virus.get(i).y] = true;
			count++;
		}
		
		while(!queue.isEmpty()) {
			node cur = queue.remove();
			
			for(int i=0; i<4; i++) {
				int nextX = cur.x + dir1[i];
				int nextY = cur.y + dir2[i];
				
				if(nextX>=0 && nextY>=0 && nextX<n && nextY<m) {
					if(modMap[nextX][nextY] == 0 && !walls[nextX][nextY]) {
						walls[nextX][nextY] = true;
						count++;
						queue.add(new node(nextX, nextY));
					}
				}
			}
		}
		return count;
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		n = s.nextInt();
		m = s.nextInt();
		map = new int[n][m];
		check = new boolean[n][m];
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				map[i][j] = s.nextInt();
				if(map[i][j] == 2) {
					virus.add(new node(i, j));
				}
				else if(map[i][j] == 1) {
					wallCount++;
				}
			}
		}
		
		selectThree(0, 0, 0);
		System.out.println(answer);
	}
}