[백준] 14502번 - 연구소 (Gold 5)

문제 링크

백준 14502번 - 연구소 (Gold 5)

문제 설명

상하좌우로 퍼질 수 있는 바이러스가 N x M 크기의 연구실에서 유출되었다.
벽을 세 개 세워서 바이러스의 유출을 최소화하고자 한다.
바이러스가 퍼지지 않는 안전 영역의 최대 크기를 구하면 된다. 단, N과 M은 3 이상 8 이하의 자연수이다.

정답 코드 및 설명

모든 경우를 탐색한다면, 벽을 세 개 세우는 가짓수가 최대 ${NM} \choose {3}$으로 5만개를 넘지 못한다.
BFS로 각각의 경우에 대해 안전 영역의 크기를 구한다면, 각 경우마다 시간 복잡도가 $O(MN)$이다.
둘을 곱해보면 N = M = 8인 경우여도 320만 정도의 수가 나오고, 2초면 이를 수행하기에 충분하다.

벽을 세 개 세우는 경우를 모두 탐색하기 위해, DFS 기법을 활용한 백트래킹을 수행하였다.
또한, 벽을 세 개 세운 후 안전 영역의 크기를 구하기 위해서는 BFS를 활용하였다.

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

public class Main {

    final static int[] xAdd = { -1, 1, 0, 0 }, yAdd = { 0, 0, -1, 1 };
    static int[][] lab;
    static int n, m, blankSize, maxSafeSize = 0;
    static boolean[][] check;
    static ArrayList<int[]> blank = new ArrayList<>();
    static int[] seq = new int[3];

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        lab = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                lab[i][j] = Integer.parseInt(st.nextToken());
                if (lab[i][j] == 0)
                    blank.add(new int[] { i, j });
            }
        }
        blankSize = blank.size();
        backTracking(0);
        bw.write(maxSafeSize + "");
        bw.close();
    }

    static void backTracking(int depth) {
        if (depth == 3) {
            int safeSize = safeSize(lab);
            if (maxSafeSize < safeSize)
                maxSafeSize = safeSize;
            return;
        }
        // 백트래킹
        for (int i = 0; i < blankSize; i++) {
            int[] wall = blank.get(i);
            if (depth != 0 && seq[depth - 1] >= i)
                continue;
            seq[depth] = i;
            lab[wall[0]][wall[1]] = 1;
            backTracking(depth + 1);
            lab[wall[0]][wall[1]] = 0;
        }
    }

    static int safeSize(int[][] currLab) {
        int safeSize = blankSize - 3;
        boolean[][] check = new boolean[n][m];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int[] loc = { i, j };
                // 바이러스 없는 칸은 패스
                if (currLab[i][j] != 2)
                    continue;
                // 이미 바이러스 있다고 체크한 칸도 패스
                if (check[i][j])
                    continue;
                // 처음 방문하는 바이러스 있는 칸
                queue.add(loc);
                check[i][j] = true;
                while (!queue.isEmpty()) {
                    int[] curr = queue.poll();
                    for (int k = 0; k < 4; k++) {
                        int x = curr[0] + xAdd[k];
                        int y = curr[1] + yAdd[k];
                        // 범위 밖이면 스킵
                        if (x < 0 || x >= n || y < 0 || y >= m)
                            continue;
                        // 이미 체크한 곳이면 스킵
                        if (check[x][y])
                            continue;
                        // 바이러스가 옮겨갈 수 있으면
                        if (currLab[x][y] == 0) {
                            check[x][y] = true;
                            queue.add(new int[] { x, y });
                            safeSize--;
                        }
                    }
                }
            }
        }
        return safeSize;
    }
}