백준 14502번: 연구소

풀이

풀이 참조
https://sihyungyou.github.io/baekjoon-14502/

• DFS로 3개의 벽을 선택
• 3개의 벽이 선택되면 BFS로 바이러스를 퍼트리고 안전공간의 크기를 구한다.

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

//벽은 꼭 3개를 세워야 한다.
public class Problem14502 {
    static int weight, height = -1;

    static int[] dirX = new int[]{0,0,1,-1};
    static int[] dirY = new int[]{1,-1,0,0};
    static int[][] map;
    static boolean[][] visited;
    static int answerMax = 0;

    //바이러스를 퍼트린 뒤 안전공간 수 반환
    public static int bfs(){
        //map의 복사
        int[][]mapDup = new int[map.length][map[0].length];
        for(int i=0; i<map.length; i++){
            System.arraycopy(map[i], 0, mapDup[i], 0, map[0].length);
        }

        visited = new boolean[mapDup.length][mapDup[0].length];
        Queue<int[]> queue = new LinkedList<>();
        int answer = 0;
        for(int i = 0; i < mapDup.length; i++){
            for(int j = 0; j < mapDup[0].length; j++){
                if(mapDup[i][j]==2){
                    queue.add(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }

        while(!queue.isEmpty()) {
            int[] currNode = queue.poll();
            for (int d = 0; d < 4; d++) {
                int newX = currNode[1] + dirX[d];
                int newY = currNode[0] + dirY[d];

                if (newX < 0 || newX >= weight || newY < 0 || newY >= height) continue;

                //4방향에 값이 존재 & 미방문
                if (mapDup[newY][newX] == 0 && !visited[newY][newX]) {
                    queue.add(new int[]{newY, newX});
                    mapDup[newY][newX] = 2;
                    visited[newY][newX] = true;
                }
            }
        }

        for(int i = 0; i < mapDup.length; i++) {
            for (int j = 0; j < mapDup[0].length; j++) {
                if (mapDup[i][j] == 0) {
                    answer++;
                }
            }
        }
        return answer;
    }

    public static void dfs(int wallNum){
        //벽 3개 설치. bfs로 안전공간 최대치 구함
        if(wallNum==3){
            int answerTemp = bfs();
            if(answerTemp > answerMax){
                answerMax = answerTemp;
            }
        } else {
            for(int i = 0; i < map.length; i++) {
                for (int j = 0; j < map[0].length; j++) {
                    if(map[i][j]==0){
                        map[i][j] = 1;
                        dfs(wallNum+1);
                        map[i][j] = 0;
                    }
                }
            }
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");

        height = Integer.parseInt(st.nextToken());
        weight = Integer.parseInt(st.nextToken());
        map = new int[height][weight];


        for(int i = 0; i < height; i++){
            String nodeStr = br.readLine();
            StringTokenizer nodeSt = new StringTokenizer(nodeStr, " ");
            for(int j = 0; j < weight; j++){
                map[i][j] = Integer.parseInt(nodeSt.nextToken());
            }
        }


        for(int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if(map[i][j]==0){



                    map[i][j] = 1;
                    dfs(1);
                    map[i][j] = 0;
                }
            }
        }

        System.out.println(answerMax);
    }
}