14502 - 연구소

1. 서론

4방향 bfs 문제이다. N, M의 범위가 8이고, 벽의 개수가 3으로 정해져 있어 어렵지 않게 풀 수 있었다.

완전탐색을해도 재귀의 깊이가 3밖에 되지 않으므로, 벽/바이러스가 하나도 없다고 생각하고 벽을 3개 세운다고 하더라도 64C3번의 연산만 하면 된다.(=41664회)

2. 풀이

문제에서 중요하게 생각해야될것은 하나이다.

벽을 세운 후, 바이러스가 퍼지는것을 구현하고 안전영역의 개수를 구해야 한다. 이 때, 바이러스가 퍼지는것은 경우의 수 때 마다 다르므로 기존맵을 복사한 후 각각 사용해야 한다.

-> 바이러스가 퍼질 때는 기존 맵에 3개의 벽을 세운 후이다. 따라서 재귀 깊이 3에 도달했을 때, 기존 맵을 복사해 새로운 맵을 만든 후 해당 맵에서 bfs를 통해 바이러스가 퍼져나가는것을 시뮬레이션하면 된다.

BFS 부분 코드

    public static void bfs(int x, int depth) {
        if (depth == 3) { // 재귀 깊이가 3일 때. 벽을 다 세웠으므로, 바이러스가 퍼져나가는것을 dfs를 통해 시뮬레이션한다.
            int result = init_safe;
            int[][] sub_map = new int[map.length][map[0].length];
            for (int i = 0; i < sub_map.length; i++) sub_map[i] = map[i].clone(); // 기존 맵을 복사해 시뮬레이션용 맵을 새로 만든다.
            Queue<Cord> queue = new LinkedList<>(virus);
            while (!queue.isEmpty()) {
                Cord elem = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = dx[i] + elem.x;
                    int ny = dy[i] + elem.y;
                    if (nx >= 0 && nx < map.length && ny >= 0 && ny < map[0].length
                            && sub_map[nx][ny] == 0) {
                        queue.add(new Cord(nx, ny));
                        sub_map[nx][ny] = 2;
                        result--;
                    }
                }
            }
            if (result > answer) answer = result;
        } else {
            for (int i = x; i < map.length; i++) {
                for (int j = 0; j < map[0].length; j++) {
                    if (map[i][j] == 0) {
                        map[i][j] = 1;
                        bfs(i, depth + 1);
                        map[i][j] = 0;
                    }
                }
            }
        }
    }

이 외에는 main에서 입력을 받고, 초깃값들을 세팅하는것 뿐이다.

전체 코드

import java.util.*;

public class P_14502 {
    static ArrayList<Cord> virus;
    static int[][] map;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0 , 0};
    static int answer;
    static int init_safe;
    static class Cord {
        int x;
        int y;

        Cord(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static void bfs(int x, int depth) {
        if (depth == 3) { // 재귀 깊이가 3일 때. 벽을 다 세웠으므로, 바이러스가 퍼져나가는것을 dfs를 통해 시뮬레이션한다.
            int result = init_safe;
            int[][] sub_map = new int[map.length][map[0].length];
            for (int i = 0; i < sub_map.length; i++) sub_map[i] = map[i].clone(); // 기존 맵을 복사해 시뮬레이션용 맵을 새로 만든다.
            Queue<Cord> queue = new LinkedList<>(virus);
            while (!queue.isEmpty()) {
                Cord elem = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = dx[i] + elem.x;
                    int ny = dy[i] + elem.y;
                    if (nx >= 0 && nx < map.length && ny >= 0 && ny < map[0].length
                            && sub_map[nx][ny] == 0) {
                        queue.add(new Cord(nx, ny));
                        sub_map[nx][ny] = 2;
                        result--;
                    }
                }
            }
            if (result > answer) answer = result;
        } else {
            for (int i = x; i < map.length; i++) {
                for (int j = 0; j < map[0].length; j++) {
                    if (map[i][j] == 0) {
                        map[i][j] = 1;
                        bfs(i, depth + 1);
                        map[i][j] = 0;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        scan.nextLine();
        map = new int[N][M];
        virus = new ArrayList<>();
        init_safe = 0; // 초기 안전영역의 크기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = scan.nextInt();
                if (map[i][j] == 2) virus.add(new Cord(i ,j));
                else if (map[i][j] == 0) init_safe++;
            }
            scan.nextLine();
        }
        init_safe -= 3; // 벽을 세울것이기 때문에, 최대 벽 개수인 3개를 미리 빼줌(안전영역이 아님)
        answer = 0;
        bfs(0, 0);
        System.out.println(answer);
    }
}