[백준 | Java] 14502 연구소

내 풀이

빈 칸인 0에 벽을 반드시 3개를 세워야하는 조건이 있다.

빈 칸에 3개의 벽을 세우는 모든 경우를 구하기 위해 DFS를 이용해 빈 칸에 3개의 벽을 세울 수 있는 모든 경우를 탐색한다.
3개의 벽이 세워진 각 경우마다 BFS로 바이러스를 퍼지게 하고, 빈 칸의 수를 세어 최대를 반환한다.

풀이과정은 다음과 같다.

1. map을 입력받은 후 DFS를 사용해 2중for문을 돌며 모든 칸을 탐색해 빈 칸을 발견하면 벽을 세운다.

2. 세운 벽의 수가 3개가 되었을 때, 안전 구역의 크기를 구한다.
   a. 안전 구역의 크기는 map을 복사한 tmp 배열에서 BFS를 사용해 바이러스를 퍼지도록 한다.

3. 바이러스가 퍼진 tmp 배열에서 안전 구역의 크기를 구한다.

import java.io.*;
import java.util.*;

// 0 => 빈 칸, 1 => 벽, 2 => 바이러스
// 벽 3개 세우기 필수
public class Main {
    static int N, M, result, max;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int[][] map, tmp;
    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];

        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());
            }
        }

        max = 0;
        dfs(0);
        System.out.println(max);
    }

    static void dfs(int cnt) {  // 아무 곳이나 벽을 3개 세우기
        if (cnt == 3) {
            countArea();
            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1;
                    dfs(cnt+1);
                    map[i][j] = 0;
                }
            }
        }
    }

    static void countArea() {
        bfs();

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

    static void bfs() {  // 바이러스 퍼지기
        Queue<int[]> queue = new LinkedList<>();
        tmp = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                tmp[i][j] = map[i][j];
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (tmp[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] xy = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = xy[0] + dx[i];
                int ny = xy[1] + dy[i];

                if (nx >= 0 && ny >= 0 && nx < N && ny < M && tmp[nx][ny] == 0) {
                    tmp[nx][ny] = 2;
                    queue.offer(new int[]{nx, ny});
                }
            }
        }
    }
}