[백준] 14502 연구소 (JAVA)

풀이

 위의 문제는 BFS와 DFS를 적당히 조합하여 푸는 문제이다. 문제를 푸는 순서는 다음과 같다. 문제에서 벽을 3개를 세워 안전구역의 최대값을 구하라고 하였다. 우리는 벽을 세우고 바이러스를 퍼트리는 일을 한번에 할수 없으니 벽을 먼저 세우고 만약 세운 벽의 개수가 3개이면 바이러스를 퍼트리는 식으로 하였다. 벽을 세우는 과정은 브루트 포스로 처음부터 끝까지 모든 경우의 수를 확인 하였고 바이러스를 퍼트리는 과정은 퍼트리기전 바이러스의 위치를 큐에 전부 넣고 큐에 있는 바이러스 위치를 토대로 하나씩 뽑아 가면서 퍼트릴수있다면 퍼트리고 큐에 추가하는 방식으로 진행하였다.

 

코드

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[][] map;
    static int[][] map_copy;
    static int n, m;
    static Queue<virus> queue = new LinkedList<>();
    static int[] dir_x = {-1, 0, 1, 0};
    static int[] dir_y = {0, 1, 0, -1};
    static int result = Integer.MIN_VALUE;
    static class virus {
        int x, y;

        public virus(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        map_copy = 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(result);
    }

    public static void DFS(int depth){
        if(depth == 3) {
            BFS();
        }
        else{
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if(map[i][j] == 0){
                        map[i][j] = 1;
                        DFS(depth+1);
                        map[i][j] = 0;
                    }
                }
            }
        }
    }

    public static void BFS(){ //바이러스 뿌리기 시작
        for (int i=0; i<n; i++){ // 지도 카피및 초기 바이러스 위치 파악
            for (int j=0; j<m; j++){
                map_copy[i][j] = map[i][j];
                if (map_copy[i][j] == 2) {
                    queue.add(new virus(i, j));
                }
            }
        }

        while(!queue.isEmpty()){
            virus point = queue.poll();
            for(int i=0; i<4; i++){
                int temp_x = point.x + dir_x[i];
                int temp_y = point.y + dir_y[i];
                if((0 <= temp_x && temp_x < n) && (0 <= temp_y && temp_y < m) && (map_copy[temp_x][temp_y] == 0)){
                    map_copy[temp_x][temp_y] = 2;
                    queue.add(new virus(temp_x, temp_y));
                }
            }
        }

        safe();
    }

    public static void safe(){
        int count = 0;
        for(int i=0; i < n ; i++){
            for (int j= 0; j<m; j++){
                if(map_copy[i][j] == 0)
                    count++;
            }
        }

        result = Math.max(count, result);
    }
}