[백준] 14502번 : 연구소 - JAVA [자바]

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

새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
-> N 과 M 의 범위(3 ≤ N, M ≤ 8) 가 작으므로
-> dfs 알고리즘을 통해 벽을 세운 모든 경우의 수의 맵을 구한다.
-> 각각의 경우의 맵에서 바이러스가 퍼졌을 때 안전구역의 수를 구한다.
-> 각 맵의 바이러스가 퍼지는 것은 bfs 알고리즘을 통해 인접한 칸에 바이러스가 퍼졌을 때의 안전구역 수를 구한다.

dfs 알고리즘을 통해 벽을 3개 세웠을 경우의 map을 구한다.

    public static void makeWallDFS(int wall) {
        if (wall == 3) {
            bfs();
            return;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                	// 벽을 세운다
                    map[i][j] = 1;
                    // 다음 벽을 세우러 간다.
                    makeWallDFS(wall + 1);
                    // 선택을 뒤로 돌려 원래(0)의 상태로 되돌린다.
                    map[i][j] = 0;
                }
            }
        }
    }

벽을 3 개 세웠을 때 바이러스가 퍼지고 난 뒤의 안전구역을 구하기 위해 bfs 알고리즘을 실행한다.

    public static void bfs() {
    	// 안전구역 수 0으로 초기화
        int safeZone = 0;
        // 원래의 맵을 수정하면 안되므로 clone하여 새로운 클론맵을 사용
        int[][] cloneMap = new int[N][M];
        // 방문 여부 초기화
        visited = new boolean[N][M];
        
        // 맵 클론
        for (int i = 0; i < N; i++) {
            cloneMap[i] = map[i].clone();
        }
        // 바이러스 위치들 큐에 삽입
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (cloneMap[i][j] == 2) queue.add(new Virus(i, j));
            }
        }
        // 모든 바이러스가 퍼질때 까지
        while (!queue.isEmpty()) {
            Virus current = queue.poll();
            visited[current.x][current.y] = true;
            // 인접한 칸이 0이면 바이러스를 퍼트리고 큐에 삽입한다.
            for (int i = 0; i < 4; i++) {
                int newX = current.x + xMove[i];
                int newY = current.y + yMove[i];

                if (newX < 0 || newX >= N || newY < 0 || newY >= M) continue;

                if (cloneMap[newX][newY] == 0) {
                    if (!visited[newX][newY]) {
                        visited[newX][newY] = true;
                        cloneMap[newX][newY] = 2;
                        queue.add(new Virus(newX, newY));
                    }
                }
            }
        }

		// 모든 바이러스가 퍼지고 난 뒤 안전구역의 수를 구한다.
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (cloneMap[i][j] == 0) {
                    safeZone++;
                }
            }
        }
        // 그전에 구한 값과 비교하여 최대 값을 업데이트한다.
        MAX = Math.max(MAX, safeZone);
    }

public class bj14502 {

    static final int[] xMove = {0, 0, 1, -1};
    static final int[] yMove = {1, -1, 0, 0};
    public static Queue<Virus> queue = new LinkedList<>();
    public static int N, M, MAX = -1;
    public static boolean[][] visited;
    public static int[][] map;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line = br.readLine();
        String[] split = line.split(" ");
        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);

        map = new int[N][M];

        for (int i = 0; i < N; i++) {
            String[] read = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(read[j]);
            }
        }

        makeWallDFS(0);
        bfs();

        bw.write(MAX + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static void makeWallDFS(int wall) {
        if (wall == 3) {
            bfs();
            return;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1;
                    makeWallDFS(wall + 1);
                    map[i][j] = 0;
                }
            }
        }
    }

    public static void bfs() {
        int safeZone = 0;
        int[][] cloneMap = new int[N][M];
        visited = new boolean[N][M];
        
        for (int i = 0; i < N; i++) {
            cloneMap[i] = map[i].clone();
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (cloneMap[i][j] == 2) queue.add(new Virus(i, j));
            }
        }
        while (!queue.isEmpty()) {
            Virus current = queue.poll();
            visited[current.x][current.y] = true;
            for (int i = 0; i < 4; i++) {
                int newX = current.x + xMove[i];
                int newY = current.y + yMove[i];

                if (newX < 0 || newX >= N || newY < 0 || newY >= M) continue;

                if (cloneMap[newX][newY] == 0) {
                    if (!visited[newX][newY]) {
                        visited[newX][newY] = true;
                        cloneMap[newX][newY] = 2;
                        queue.add(new Virus(newX, newY));
                    }
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (cloneMap[i][j] == 0) {
                    safeZone++;
                }
            }
        }
        MAX = Math.max(MAX, safeZone);
    }

    public static class Virus {
        int x;
        int y;

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