골드 4 난이도의 문제이다.
이전에 푼 문제와 비슷한 유형의 문제라서 생각보다 간단하게 해결할 수 있었다.

풀이

1. 벽을 세울 위치는 조합을 통해 구성한다.
2. 구성한 벽의 위치를 토대로 입력값인 originMap(원본)을 복제한 afterMap에 새로 세울 벽을 표시해준다.
3. 벽이 세워진 afterMap의 바이러스 좌표 각각에서 bfs 혹은 dfs로 탐색을 하며 바이러스를 퍼트린다.
4. 바이러스가 전부 퍼진 후의 안전구역 크기를 구해서 result에 저장한다.
5. 다음 벽 조합에서 위 과정을 반복하고 4번의 값과 새로운 벽 조합에서 구한 안전구역 크기를 비교해서 result를 더 큰 값으로 업데이트한다.

코드

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

public class Main {

    static int[][] originMap;
    static int[][] afterMap;
    static int WALL_COUNT = 3;
    static int N, M;
    static List<Point> virus;   // 바이러스 좌표
    static List<Point> empty;   // 벽이 될 수 있는 좌표
    static List<Point> choice;   // 선택된 벽의 좌표 (조합의 결과)
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int result = Integer.MIN_VALUE;
    static boolean[] wall_visited;
    static boolean[][] virus_visited;

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

        originMap = new int[N][M];
        virus = new ArrayList<>();
        empty = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                originMap[i][j] = Integer.parseInt(st.nextToken());
                if (originMap[i][j] == 2) virus.add(new Point(i, j));
                if (originMap[i][j] == 0) empty.add(new Point(i, j));
            }
        }
        wall_visited = new boolean[empty.size()];
        choice = new ArrayList<>();

        func(0, 0);
        System.out.println(result);
    }

    public static void func(int start, int count) {
        if (count == WALL_COUNT) {
            //  조합으로 선택된 벽을 세워서 afterMap을 구성
//            afterMap = originMap;     -> 이런식으로 map을 복제하면 안됨. originMap도 변경될 수 있음
            afterMap = new int[N][M];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    afterMap[i][j] = originMap[i][j];
                }
            }
            for (Point c : choice) afterMap[c.x][c.y] = 1;

            //  모든 바이러스의 위치에서 그래프 탐색을 통해 바이러스가 최대한 퍼져나가도록 함
            virus_visited = new boolean[N][M];
            for (Point v : virus) {
                bfs(v, virus_visited);
            }

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

        //  조합을 통해 벽을 세울 위치를 구성
        for (int i = start; i < empty.size(); i++) {
            if (!wall_visited[i]) {
                wall_visited[i] = true;
                choice.add(empty.get(i));
                func(i + 1, count + 1);
                choice.remove(empty.get(i));
                wall_visited[i] = false;
            }
        }
    }

    public static void bfs(Point point, boolean[][] virus_visited) {
        Queue<Point> q = new LinkedList<>();
        q.add(point);
        virus_visited[point.x][point.y] = true;

        while (!q.isEmpty()) {
            Point start = q.poll();
            for (int i = 0; i < 4; i++) {
                int newX = start.x + dx[i];
                int newY = start.y + dy[i];

                if ((newX >= 0 && newX < N) && (newY >= 0 && newY < M)) {   //  바이러스의 범위 체크
                    if (afterMap[newX][newY] == 0 && !virus_visited[newX][newY]) {
                        q.add(new Point(newX, newY));
                        virus_visited[newX][newY] = true;
                        afterMap[newX][newY] = 2;
                    }
                }
            }

        }
    }

    public static class Point {
        int x, y;

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

주의할 점

위 코드를 보면 map을 복제하는 부분에 주석처리 되어있는 부분이 있는데, 처음에는 그냥 무작정 저런 식으로 복제를 했었는데 결과값이 이상하게 나와서 찾아보니, 저런식으로 복제를 할 경우 얕은복사라고 해서 원본 객체의 참조만을 복제하는 거라서 같은 메모리 주소를 참조하게되고, afterMap을 변경할 때 originMap 또한 변경이 발생한다고한다. 이럴 때는 그냥 반복문으로 깊은복사를 해서 원본 객체의 데이터를 새로운 객체에 완전히 복제해야한다.

리뷰

직전에 푼 문제가 조합을 사용하는 문제였어서 딱 이 문제를 읽었을 때 조합을 사용해야한다고 느꼈다. 확실히 문제를 많이 풀어야 처음 읽었을 때 어떤 알고리즘을 사용해서 풀어야하는 지 알 수 있을 거 같다.
BFS/DFS를 어느정도 이해하고 외웠다고 생각했는데 약간씩 헷갈린다. 기본적인 알고리즘이니 더 확실하게 해야겠다.
그래도 골드4의 문제를 다른 사람의 풀이를 보지 않고 스스로 풀어내서 뿌듯했다.