[BAEKJOON] 14502 연구소 (Java)

[ 문제 ]

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0

0 0 1 0 1 2 0

0 1 1 0 1 0 0

0 1 0 0 0 0 0

0 0 0 0 0 1 1

0 1 0 0 0 0 0

0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0

1 0 1 0 1 2 0

0 1 1 0 1 0 0

0 1 0 0 0 1 0

0 0 0 0 0 1 1

0 1 0 0 0 0 0

0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2

1 0 1 0 1 2 2

0 1 1 0 1 2 2

0 1 0 0 0 1 2

0 0 0 0 0 1 1

0 1 0 0 0 0 0

0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

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

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

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

출력

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

[ 핵심풀이 ]

bfs와 완전탐색이 합해진 문제이다.

0) 연구소 지도에 벽 3개를 세울 수 있는곳을 정한다

1) 벽을세운뒤 바이러스를 퍼트린다

2) 남아있는 안전영역의 수를 구하고, 맵을 원래대로 돌린뒤 다시 0으로 돌아간다.

 

Map자체를 복사해서 사용후 버릴수있고,

Map을 바꾼뒤 1~2를 수행후 되돌리는 방식이 있겠다.

나는 후자를 택하여 다음과같이 진행된다

[ 핵심소스 ]

static int solve() {
    for(boolean item[] : visit)
        Arrays.fill(item, false);
    for(int i=0;i<3;i++) {
        int y = safe.get(choice[i]).y;
        int x = safe.get(choice[i]).x;
        map[y][x] = 1;
    }
    spread_virus();
    int ret = find_safezone();
    for(int i=0;i<3;i++) {
        int y = safe.get(choice[i]).y;
        int x = safe.get(choice[i]).x;
        map[y][x] = 0;
    }
    return ret;
}

1) 선택된 3개의 벽을 세워주고

-> spread_virus() : 바이러스를 퍼트린 후

-> find_safezone() : 안전영역의 수를 구한뒤

2) 맵을 되돌린다

[ Java ]

import java.io.*;
import java.util.*;
public class _14502_연구소 {
    static final int MAX = 10;
    static int H, W, answer;
    static int ay[] = {-1,1,0,0};
    static int ax[] = {0,0,-1,1};
    static int map[][] = new int[MAX][MAX];
    static boolean visit[][] = new boolean[MAX][MAX];
    static class xy {
    int y, x;
        xy(int y, int x) {
            this.y=y;
            this.x=x;
        }
    }
    static ArrayList<xy>virus = new ArrayList<>();
    static ArrayList<xy>safe = new ArrayList<>();
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        for(int i=0;i<H;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<W;j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 2)
                    virus.add(new xy(i, j));
                if (map[i][j] == 0)
                    safe.add(new xy(i, j));
            }
        }
        select(0, 0);
        System.out.println(answer);
    }
    static int choice[] = new int[3];
    static boolean check[] = new boolean[65];
    static void select(int index, int cnt) {
        if (cnt==3) {
            int result = solve();
            answer = answer > result ? answer : result;
            return;
        }
        for(int i=index;i<safe.size();i++) {
            if(!check[i]) {
                check[i]=true;
                choice[cnt]=i;
                select(i+1, cnt+1);
                check[i]=false;
            }
        }
    }
    static int solve() {
        for(boolean item[] : visit)
            Arrays.fill(item, false);
        for(int i=0;i<3;i++) {
            int y = safe.get(choice[i]).y;
            int x = safe.get(choice[i]).x;
            map[y][x] = 1;
        }
        spread_virus();
        int ret = find_safezone();
        for(int i=0;i<3;i++) {
            int y = safe.get(choice[i]).y;
            int x = safe.get(choice[i]).x;
            map[y][x] = 0;
        }
        return ret;
    }
    static void spread_virus() {
        Queue<xy>q = new LinkedList<>();
        for(int i=0;i<virus.size();i++) {
            int y = virus.get(i).y;
            int x = virus.get(i).x;
            q.add(new xy(y, x));
            visit[y][x] = true;
        }
        while(!q.isEmpty()) {
            xy out = q.poll();
            for(int i=0;i<4;i++) {
                int ny = out.y+ay[i];
                int nx = out.x+ax[i];
                if(!range(ny, nx) && map[ny][nx] == 0 && !visit[ny][nx]) {
                    visit[ny][nx] = true;
                    q.add(new xy(ny, nx));
                }
            }
        }
    }
    static int find_safezone() {
        int cnt=0;
        Queue<xy>q = new LinkedList<>();
		for(int s=0;s<safe.size();s++) {
            int y = safe.get(s).y;
            int x = safe.get(s).x;
            if (map[y][x] == 0 && !visit[y][x]) {
                q.add(new xy(y, x));
                visit[y][x] = true;
                while(!q.isEmpty()) {
                    xy out = q.poll();
                    cnt++;
                    for(int i=0;i<4;i++) {
                        int ny = out.y+ay[i];
                        int nx = out.x+ax[i];
                        if(!range(ny, nx) && map[ny][nx] == 0 && !visit[ny][nx]) {
                            visit[ny][nx] = true;
                            q.add(new xy(ny, nx));
                        }
                    }
                }
            }
        }
        return cnt;
    }
    static boolean range(int y, int x) {
        return y<0||x<0||y>H-1||x>W-1;
    }
}