Java - [BOJ]14502 - 연구소

출처

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

 

문제

격자모양의 구조로 되어있는 연구소에 바이러스가 유출되었다. 바이러스는 상하좌우 빈칸이 있는곳으로 퍼질 수 있으며, 벽이 있으면 진행이 불가능하다.

 

벽을 새로 3개만 세워 바이러스 유출을 최대한 막아 안전지대를 확보한다고 하였을 때, 가장 넓은 안전지대의 면적을 구하는 문제이다.

 

풀이

정석적인 DFS + BFS 문제이다.

 

먼저, 벽을 3개를 막아야 하는데 어느 벽을 막아야 안전지대가 가장 넓은지 직접 세워보기 전까지는 알 수 없기때문에, 모든 경우를 살펴보아야 한다. 또한 3개를 막기 위한 벽 위치의 조합을 구하기 위해서는, DFS를 이용해야 한다.

 

DFS를 이용하여 세개의 벽을 막아놓았다면, 이후 막혀있는 연구실에서 BFS를 이용하여 바이러스를 상하좌우로 번식시킨 뒤, 안전지대의 넓이를 세어 가장 넓은 면적을 구하면 되는 간단한 문제이다. (물론 구현 자체는 간단하지는 않다)

 

자세한 풀이는 아래를 참조

 

코드

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

public class Main {
    static int[][] map;
    static int N, M, answer;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};


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


        map = new int[N][M];
        answer = 0;
        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());
            }
        }

        dfs(0);
        
        bw.write(answer + "\n");
        br.close();
        bw.flush();
        bw.close();
    }

    static void dfs(int cnt) {
        if (cnt == 3) {
            answer = Math.max(afterVirus(), answer);
            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(cnt + 1);
                    map[i][j] = 0;
                }
            }
        }

    }

    public static int[][] copyArr() {
        int[][] temp = new int[N][M];
        for (int i = 0; i < N; i++) {
            temp[i] = map[i].clone();
        }
		return temp;
    }

    static int afterVirus() {
        Deque<int[]> q = new ArrayDeque<>();
        int[][] tmp = copyArr();

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if (map[i][j] == 2) {
                    q.addFirst(new int[]{i, j});
                }
            }
        }
        
        while (!q.isEmpty()) {
            int[] now = q.pollLast();
            for (int i = 0; i < 4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (isRange(nx, ny) && tmp[nx][ny] == 0) {
                    q.addFirst(new int[]{nx, ny});
                    tmp[nx][ny] = 2;
                }
            }
        }
        return checkSafe(tmp);
    }

    public static int checkSafe(int[][] temp) {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (temp[i][j] == 0) {
                    cnt++;
                }
            }
        }
        return cnt;
    }

    static boolean isRange(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }

}