[Java] 백준 연구소

1. 문제분석

연구실 공간에 바이러스가 존재한다. 이 바이러스는 사방면으로 퍼져나간다고 한다.

하지만 우리는 벽을 3개 세울 수 있다. 이 3개로 최대한 바이러스가 안퍼져나가게 해야한다.

이 3개를 항상 최적으로 구해서 대입하고 바로 빈공간을 구할 수 없다.

여기서 볼 점은 벽 3개를 여러 곳에 넣어보고 그 때 빈 공간이 최대인 곳을 구하는 것이다.

 

그렇다면 벽 3개를 여러군데 넣어주는 것을 어떻게 할까?

바로 DFS를 통해서 넣어주면 된다. 만약 벽을 3개 세웠다면 바이러스가 퍼져나간 후 빈공간을 구하면 되는 것이다.

    static void setWall(int count) {
        if (count == 3) {
            bfs();
        } else {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] == 0) {
                        map[i][j] = 1;
                        setWall(count + 1);
                        map[i][j] = 0;
                    }
                }
            }
        }
    }

map은 현재 연구소의 지도다. 빈 공간만 벽을 세울 수 있으므로 0일 때 1로 만들고 count를 1 더해준다.

여기서 볼 점은 다시 세운 벽을 치운다는 것이다. 그래야 여러 공간을 세울 수 있을 것이다.

 

static void bfs() {
        int[][] copyMap = new int[N][M];
        Queue<Pos> queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                copyMap[i][j] = map[i][j];
                if (copyMap[i][j] == 2) {
                    queue.offer(new Pos(i, j));
                }
            }
        }
        while (!queue.isEmpty()) {
            Pos p = queue.poll();
            for (int i = 0; i < 4; i++) {
                int moveX = p.x + dx[i];
                int moveY = p.y + dy[i];
                if(check(moveX, moveY) && copyMap[moveX][moveY] == 0){
                    copyMap[moveX][moveY] = 2;
                    queue.offer(new Pos(moveX,moveY));
                }
            }
        }
        maxBlankArea = Math.max(maxBlankArea, getBlankArea(copyMap));
    }

필자는 벽이 3개일 때 BFS를 통해서 바이러스가 퍼져나가는 것을 구했다.

DFS로는 해보지 않았지만 경로를 구하는 것이 아닌 단순 전체 퍼져나가기 때문에 BFS를 사용했다.

 

주의점은 2차원 배열은 얕은 복사가 된다는 것이다.

2중 for문으로 직접 데이터를 넣으며 바이러스인 지점은 큐에 넣어주었다.

 

바이러스가 퍼져나가는 것은 델타탐색으로 상하좌우로 움직였다.

빈 공간이면서 인덱스 범위를 나가지 않는다면 해당 부분을 바이러스로 변경하고 큐에 넣어준다.

    static int getBlankArea(int[][] map){
        int count = 0;
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                if(map[i][j] == 0){
                    count++;
                }
            }
        }
        return count;
    }

마지막으로 빈공간을 구해주고 최대 빈공간을 구하면 된다.

2. 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Pos {
    int x, y;

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

public class Main {

    static int N, M;
    static int[][] map;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int maxBlankArea = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());
            }
        }
        setWall(0);
        System.out.println(maxBlankArea);
    }

    //3개까지만 벽을 무작위로 생성해보자.
    static void setWall(int count) {
        if (count == 3) {
            bfs();
        } else {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] == 0) {
                        map[i][j] = 1;
                        setWall(count + 1);
                        map[i][j] = 0;
                    }
                }
            }
        }
    }

    static boolean check(int x, int y) {
        if (x < 0 || x >= N) return false;
        if (y < 0 || y >= M) return false;
        return true;
    }

    static void bfs() {
        int[][] copyMap = new int[N][M];
        Queue<Pos> queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                copyMap[i][j] = map[i][j];
                if (copyMap[i][j] == 2) {
                    queue.offer(new Pos(i, j));
                }
            }
        }
        while (!queue.isEmpty()) {
            Pos p = queue.poll();
            for (int i = 0; i < 4; i++) {
                int moveX = p.x + dx[i];
                int moveY = p.y + dy[i];
                if(check(moveX, moveY) && copyMap[moveX][moveY] == 0){
                    copyMap[moveX][moveY] = 2;
                    queue.offer(new Pos(moveX,moveY));
                }
            }
        }
        maxBlankArea = Math.max(maxBlankArea, getBlankArea(copyMap));
    }

    static int getBlankArea(int[][] map){
        int count = 0;
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                if(map[i][j] == 0){
                    count++;
                }
            }
        }
        return count;
    }
}

어쩌다 보니 분석에서 구현을 전부 설명했다. 여기서 주의할 점을 골라보자.

1. 2차원 배열은 얕은복사(주소값까지)가 된다. 인덱스마다 값을 넣어주자

2. 3개를 억지로 찾을려고 하지말자. DFS를 통해 3개를 고르면 BFS로 바이러스를 퍼트리자

 

이 문제는 DFS, BFS 기초만 알아도 풀 수 있는 문제다. 구글링을 해서 봤다면 반드시 혼자서도 코딩해보자.

3. 마무리

머리가 굳은건지 요즘 vue에 대해 배우다 보니 알고리즘을 다 까먹었다.