문제
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.
이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.
2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.
바이러스가 퍼진 뒤의 모습은 아래와 같아진다.
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.
출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
구현코드
import java.util.*;
import java.io.*;
class Node{
private int x;
private int y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
public int getX(){
return x;
}
public int getY(){
return y;
}
}
public class Main{
public static int n;
public static int m;
public static int max;
public static int[][] map;
public static ArrayList<Node>virus;
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());
map = new int[n][m];
virus = new ArrayList<>();
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());
// 값이 2 이면 바이러스(ArrayList)에 x,y 값 추가
if(map[i][j] == 2) virus.add(new Node(i, j));
}
}
// c최대값을 0으로 초기화 후 dfs(벽세우기) 시작
max = 0;
dfs(0);
System.out.println(max);
}
public static void dfs(int depth){
// 벽을 3개 세우면 bfs(바이러스) 전파시작
if(depth == 3){
bfs();
return;
}
for(int i = 0; i < n ; i++){
for(int j = 0; j < m ; j++){
// 값이 0이면 벽을 세울수 있기 때문에 벽 세우고 재귀함수 호출
if(map[i][j] == 0){
map[i][j] = 1;
dfs(depth+1);
map[i][j] = 0;
}
}
}
}
public static void bfs(){
// 바이러스는 상하 좌우로 갈수있기 때문에 값 선언
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, 1, -1};
//깊은 복사 를 통한 배열 복사
int[][] mapCopy = new int[n][m];
for(int i = 0 ; i < n ; i ++) {
for(int j = 0 ; j < m ; j ++) {
mapCopy[i][j] = map[i][j];
}
}
// 큐 선언 후 바이러스 넣기 dfs 호출전에 넣는게 더 효율적인거 같음 -> 전역변수로 선언하기
Queue<Node>queue = new LinkedList<>();
for( Node n: virus) {
queue.offer(n);
}
// queue 가 없을때 까지 반복
while(!queue.isEmpty()){
Node now = queue.poll();
// 상하좌우 탐색
for(int index = 0; index < 4 ; index++){
int nx = now.getX() + dx[index];
int ny = now.getY() + dy[index];
// 좌표값을 넘지 않으면서 벽을 넘지 않은범위를 바이러스퍼트리기.
if(0 <= nx && nx < n && 0<= ny && ny < m && mapCopy[nx][ny] == 0 ){
mapCopy[nx][ny] = 2;
queue.offer(new Node(nx, ny));
}
}
}
int cnt = 0;
// 바이러스가 퍼지지 않은 범위를 카운트
for(int j = 0; j <n ; j++){
for(int k = 0 ; k < m; k++){
if(mapCopy[j][k] == 0) cnt++;
}
}
//최대값 구하기
max = Math.max(max, cnt);
}
}코드해석
조금 까라로운 문제였다. 벽을 세워야하고 벽을 세운곳에서 바이러스틑 전파시켜야하고 그걸 모든 경우의수를 반복시켜야하는 문제이다.
벽을 세우는 것은 DFS 기반의 백트레킹을 사용하였다.배열만큼을 반복하여 만약 배열 값이 0이라면 1로 바꿔주고 dfs(depth+1) 해준 후에 다시 배열값을 0으로 바꿔준다. 이때 depth 가 3이되면 BFS 를 실행시킨다. 이때 BFS 는 바이러스를 전파시키는 것 우선 바이러스는 상 하 좌 우 로 퍼질 수있기 때문에 dx,dy 를 선언 후에 배열을 깊은복사로 복사 시켜준다. 또한 바이러스 개수 만큼 queue 에 넣어준 후에 반복문 실행시킨다.
반복문에서는 큐를 뺀 후에 상하좌우 만큼 반복시키고 그때 nx,ny 값이 좌표를 넘어서지 않고 벽을 넘지 않는 범위를 체크 한 후에 배열 값을 2로 변경 후에 큐에 값을 넣어준다. 그후 max 값을 구해준다.
이걸 모두 반복해주면 된다.
