[Java][자바][백준][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개 이상이다.

출력

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

 

생각

전형적인 bfs 문제이다. 3개의 벽을 세우는데 어떤 상황에서 가장 안전영역이 많을지는 조합을 사용하였다. 벽을 세울 수 있는 곳의 인덱스를 찾아서 그 중에서 3개의 벽을 세워 bfs 후, 안전영역을 구했다.

안전영역을 각각 arrayList에 넣은 후, 마지막에 최대값을 출력하였다.

 

순열과 조합은 생각보다 많이 쓰이는 것 같다. C++에는 next ~해서 순열,조합 라이브러리가 있지만 자바는 없으므로 하는 법을 잘 알아두도록 하자!! 정리는 해두었는데, 아직 포스팅을 못했다. ㅠㅠ

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int map[][];
    static boolean visited[][];
    static int wall = 3;
    static int x,y;
    static ArrayList<int[]> comb_arr = new ArrayList<int[]>();
    static ArrayList<Integer> secure_area = new ArrayList<Integer>(); 
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());
        
        map = new int[x][y];
        visited = new boolean[x][y];
        
        for(int i=0; i<x; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<y; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    
        int tmp_zero_index = 0;
        int zero_count = 0;
        ArrayList<Integer> zero_index = new ArrayList<Integer>(); 
        
        //map을 돌면서 0인것의 번호 찾기.-> 인덱스는 번호/배열의 길이 번호%배열의 길이로 좌표 구한다.
        for(int i=0; i<x; i++) {
            for(int j=0; j<y; j++) {
                if(map[i][j] == 0) {
                    zero_index.add(tmp_zero_index);
                    zero_count++;
                }
                tmp_zero_index++;
            }
        }
        
        //0인 것의 번호 중 앞에서부터 3개 뽑기 (조합)
        //-1을 넣어서 마지막꺼 까지 들어갈 수 있게 만들었다. 후에 사이즈에 신경써야한다.
        int[] arr = new int[wall];
        zero_index.add(-1);
        doCombination(arr, 0, -1, 3, zero_index, 0);
        //조합을 구해 여러번 해야하므로 map을 deepCopy하여 문제를 풀었다.
        for(int i=0; i<comb_arr.size(); i++) {
            int[][] map_clone = deepCopy(map);
            
            for(int j=0; j<wall; j++) {
                int tmp_x = comb_arr.get(i)[j] / y;
                int tmp_y = comb_arr.get(i)[j] % y;
                map_clone[tmp_x][tmp_y] = 1;
            }
                        
            for(int a=0; a<x; a++) {
                for(int b=0; b<y; b++) {
                    if(!visited[a][b] && map_clone[a][b] == 2) {
                        bfs(map_clone, a, b);
                    }
                }
            }
            
            secure_area.add(countZero(map_clone));
            for(int k=0; k<x; k++) {
                Arrays.fill(visited[k], false);
            }
        }
        
        System.out.println(Collections.max(secure_area));
    }
    //조합 - arr 배열에서 n개 중 r개를 뽑는 방법이다.
    public static void doCombination(int[] arr, int index, int n, int r, ArrayList<Integer> zero_arr , int target){
         
        if(r == 0){
            int[] tmp = new int[wall];
            for(int i=0; i<wall; i++) {
                tmp[i] = arr[i];
            }
            comb_arr.add(tmp);
        } else if(zero_arr.get(target) == n){ 
            return;
        } else{
            arr[index] = zero_arr.get(target);
  
            doCombination(arr, index+1, n, r-1, zero_arr, target+1);
            doCombination(arr, index, n, r, zero_arr, target+1);
        }
    }
    
    public static void bfs(int[][] arr, int a , int b) {
        Queue<dot> q = new LinkedList<dot>();
        visited[a][b] = true;
        q.add(new dot(a,b));
        
        while(!q.isEmpty()) {
            dot t = q.remove();
            int x1 = t.x;
            int y1 = t.y;
            
            for(int i=0; i<4; i++) {
                int x2 = x1 + dx[i];
                int y2 = y1 + dy[i];
                
                if(x2>=0 && x2<x && y2>=0 && y2<y && !visited[x2][y2] && arr[x2][y2] == 0) {
                    q.add(new dot(x2,y2));
                    visited[x2][y2] = true;
                    arr[x2][y2] = 2;
                }
            }
        }
    }
    
    public static int countZero(int[][] arr) {
        int zero_count = 0;
        
        for(int i=0; i<x; i++) {
            for(int j=0; j<y; j++) {
                if(arr[i][j] == 0) {
                    zero_count++;
                }
            }
        }
        
        return zero_count;
    }
    
    public static int[][] deepCopy(int[][] original) {
        if(original == null) return null;
        
        int[][] result = new int[original.length][original[0].length];
        
        for(int i=0; i<original.length; i++) {
            System.arraycopy(original[i], 0, result[i], 0, original[0].length);
        }
        
        return result;
    }
}
 
class dot {
    int x;
    int y;
    
    public dot(int x, int y) {
        this.x = x;
        this.y = y;
    }
}