[Baekjoon Online Judge] 14502번: 연구소

14502번: 연구소

요구사항

 - 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
 - 연구소는 크기가 N x M인 직사각형으로 나타낼 수 있다.
 - 연구소는 빈 칸, 벽으로 이루어져 있다. 벽은 칸 하나를 차지한다.
 - 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
 - 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
 - 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다.

입력

 - 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

 - 둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

 - 빈 칸의 개수는 3개 이상이다.

출력

 첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Baekjoon14502 {

    static int n, m;
    static int[][] map;
    static int[][] virusMap;
    static int[] xMove = {-1, 1, 0, 0};
    static int[] yMove = {0, 0, -1, 1};
    static int max;

    static class Location {
        int x, y;
        public Location(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    // dfs + 백트래킹으로 3개의 벽 세우기
    public static void dfs(int count) {
        if (count == 3) { // 벽 3개를 세웠을 때
            bfs();        // 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; // 벽 세우기
                    dfs(count + 1);
                    map[i][j] = 0; // 벽 허물기
                }
            }
        }
    }

    private static void bfs() {
        virusMap = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                virusMap[i][j] = map[i][j];
            }
        }

        Queue<Location> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) { // queue에 바이러스를 담는다.
            for (int j = 0; j < m; j++) {
                if (virusMap[i][j] == 2) {
                    queue.add(new Location(i, j));
                }
            }
        }

        while (!queue.isEmpty()) {
            Location location = queue.poll();
            int pollX = location.x;
            int pollY = location.y;

            for (int i = 0; i < 4; i++) { // 4방향 탐색
                int x = pollX + xMove[i];
                int y = pollY + yMove[i];
                if (isLocation(x, y)) { // 벽이 아닌 곳이면 바이러스를 퍼트린다.
                    virusMap[x][y] = 2;
                    queue.add(new Location(x, y));
                }
            }
        }
        max = Math.max(max, countSafeArea()); // 안전구역의 값을 갱신한다.
    }

    private static boolean isLocation(int x, int y) {
        if (x >= 0 && y >= 0 && x < n && y < m && virusMap[x][y] == 0) return true;
        return false;
    }

    // 안전 구역의 개수를 count한다.
    private static int countSafeArea() {
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (virusMap[i][j] == 0) {
                    ++count;
                }
            }
        }
        return count;
    }

    private static void print(int[][] map) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = bufferedReader.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            input = bufferedReader.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }
//        print(map);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1;
                    dfs(1);
                    map[i][j] = 0;
                }
            }
        }

        bufferedWriter.write(String.valueOf(max));

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

 

 백트래킹 + DFS + BFS를 활용해야 하는 문제이다. 벽을 3개 세우는 모든 경우를 탐색하여 각각의 상황에서 바이러스가  가장 적에 퍼져 있는, 즉 안전 구역이 많은 경우에 값을 출력하여 구현하였다. 기준이 되는 map과 virusMap을 나눈 이유는 기존의 map을 재사용하기에는 변화된 부분이 많이 때문에 새로운 map을 활용하여 값을 복사하여 사용하였다.