[백준] 14502. 연구소 - JAVA

1. 문제

https://www.acmicpc.net/problem/14502

 

2. 풀이 과정

이 문제는 N x M 크기의 맵이 주어지고, 각 영역은 빈 칸(0), 벽(1), 바이러스(2)로 구분된다.

바이러스는 벽을 통과 못한다. 벽 3개를 추가로 설치할 수 있으며, 이 때 안전 영역의 최대 개수를 구하는 문제이다.

 

N, M의 최대크기는 8인데 제한시간이 2초로 비교적 여유롭다.

 

문제 접근

1. 3개의 벽을 치는 모든 케이스를 모두 구한다.

• DFS, 백트래킹을 통해 3개의 벽을 치는 모든 케이스를 구한다.
• 각 케이스 마다 BFS를 통해 감염처리를 하고 안전영역의 개수를 구해서 최대값을 갱신한다.

static void dfs(int depth) {
    if (depth == 3) {
        // 3개의 벽을 모두 설치한 상태
        MAX = Math.max(MAX, safeZone);
        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(depth + 1);
                map[i][j] = 0;
            }
        }
    }
}

 

2. 각 케이스마다 BFS를 통해 감염 영역을 확장해간다.

• 여기서 중요한 것은 여러 케이스를 고려해야 하기 때문에, map(원본 배열)을 사용하지 않는다.
• 복사본을 사용하여 감염처리를 한다.

static int bfs() {
    Queue<Point> q = new LinkedList<>();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 2) {
                q.offer(new Point(i, j));
            }
        }
    }
    int[][] copyMap = new int[N][M];
    for (int i = 0; i < N; i++) {
        copyMap[i] = map[i].clone();
    }

    while (!q.isEmpty()) {
        Point cur = q.poll();
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M || copyMap[nx][ny] != 0) {
                continue;
            }
            q.offer(new Point(nx, ny));
            copyMap[nx][ny] = 2;
        }
    }
    
    return getSafeZone(copyMap); // 안전 영역 개수를 구한다.
}

 

3. 각 케이스마다 안전 영역의 개수를 구하고, 최댓값으로 갱신하다.    

• 0인 영역을 카운트 해서 반환한다.

static int getSafeZone(int[][] copyMap) {
    int safeZone = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (copyMap[i][j] == 0) {
                safeZone++;
            }
        }
    }
    return safeZone;
}

MAX = Math.max(MAX, safeZone); // 최댓값 갱신

 

3. 코드

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    static int N;
    static int M;
    static int[][] map;

    static int MAX = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        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());
            }
        }

        // 벽을 3개 생성하는 모든 방법을 구한다.(DFS)
        dfs(0);

        bw.write(MAX + "\n");
        bw.flush();
        bw.close();
    }

    static void dfs(int depth) {
        if (depth == 3) {
            int safeZone = bfs(); // BFS를 통해 감염 시킨다.
            MAX = Math.max(MAX, safeZone);
            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(depth + 1);
                    map[i][j] = 0;
                }
            }
        }
    }

    static int bfs() {
        Queue<Point> q = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 2) {
                    q.offer(new Point(i, j));
                }
            }
        }
        int[][] copyMap = new int[N][M];
        for (int i = 0; i < N; i++) {
            copyMap[i] = map[i].clone();
        }

        while (!q.isEmpty()) {
            Point cur = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M || copyMap[nx][ny] != 0) {
                    continue;
                }
                q.offer(new Point(nx, ny));
                copyMap[nx][ny] = 2;
            }
        }
        return getSafeZone(copyMap); // 안전 영역 개수를 구한다.
    }

    static int getSafeZone(int[][] copyMap) {
        int safeZone = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (copyMap[i][j] == 0) {
                    safeZone++;
                }
            }
        }
        return safeZone;
    }

    static class Point {
        int x;
        int y;

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