[백준] 연구소

문제

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

14502번: 연구소

 

문제 분석

• n * m 크기의 맵이 주어지는데 0은 빈칸, 1은 벽, 2는 바이러스이다.
• 바이러스는 상하좌우 인접한 빈칸으로 퍼져 나간다. 바이러스가 최소한으로 퍼져 나가도록 벽을 3개 세워야 하는 문제이다.
• n 과 m 은 모두 3 이상 8 이하이다.
  • 크기가 작기 때문에 완전 탐색을 생각해볼 수 있을 거 같다.
• 주어지는 바이러스의 개수는 2보다 크거나 같고 10보다 작거나 같다.

 

우선 바이러스가 퍼져 나가는 것을 따져보면 바이러스 부터 상하좌우 주변으로 퍼지기 때문에 BFS 알고리즘을 사용하면 될 거 같다.

문제는 벽을 어떻게 3개 세우느냐 인데... 사람 눈으로 풀어도 최선으로 벽을 세우는 방법을 찾는 것이 쉽지 않다.

아까 맵의 크기가 충분이 작기 때문에 완전탐색으로 벽을 세우는 방법을 찾는 것도 가능해 보인다.

 

 

1. 빈 공간 좌표를 담고 있는 리스트를 생성한다.

2. 해당 리스트로 부터 3개를 뽑는 방법을 완전탐색하고 탐색 리스트에 넣어 둔다.

3. 탐색 리스트를 돌면서 BFS를 통해 바이러스를 전파시킨다.

4. 빈 칸이 제일 적은 값을 반환한다.

 

코드

package Backjoon;

import java.util.*;

/**
 * 연구소
 * https://www.acmicpc.net/problem/14502
 */
public class Laboratory {
    final static int WALL_CNT = 3;
    final static int[][] moves = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    static List<List<Integer>> wallList = new ArrayList<>();
    static List<Vertex> virusList = new ArrayList<>();
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] map = new int[n][m];
        int maxEmptySpace = 0;
        List<int[]> emptySpaces = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = scanner.nextInt();

                if (map[i][j] == 0) {
                    emptySpaces.add(new int[]{i, j});
                }else if(map[i][j] == 2){
                    virusList.add(new Vertex(i, j));
                }
            }
        }

        backtracking(0, emptySpaces, new ArrayList<>());

        for (List<Integer> walls : wallList) {
            int[][] newMap = createNewMap(map, walls, emptySpaces);

            // BFS 코드
            Queue<Vertex> queue = new LinkedList<>();

            for (Vertex virus : virusList) {
                queue.offer(virus);
                newMap[virus.r][virus.c] = 2;
            }

            while (!queue.isEmpty()) {
                Vertex cur = queue.poll();

                for (int[] move : moves) {
                    int nextR = cur.r + move[0];
                    int nextC = cur.c + move[1];

                    if (nextR >= 0 && nextR < map.length && nextC >= 0 && nextC < map[0].length) {
                        Vertex nextVertex = new Vertex(nextR, nextC);
                        if (newMap[nextR][nextC] == 0) {
                            queue.offer(nextVertex);
                            newMap[nextR][nextC] = 2;
                        }
                    }
                }
            }

            int emptySpaceCnt = countEmptySpace(newMap);
            maxEmptySpace = Math.max(maxEmptySpace, emptySpaceCnt);
        }

        System.out.println(maxEmptySpace);
    }

    static class Vertex{
        private int r;
        private int c;

        public Vertex(int r, int c){
            this.r = r;
            this.c = c;
        }
    }

    static int countEmptySpace(int[][] map){
        int count = 0;

        for (int i=0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (map[i][j] == 0) {
                    count++;
                }
            }
        }

        return count;
    }

    static int[][] createNewMap(int[][] map, List<Integer> walls, List<int[]> emptySpaces) {
        int[][] newMap = new int[map.length][map[0].length];

        for (int i=0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                newMap[i][j] = map[i][j];
            }
        }

        for (int wallIdx : walls) {
            int[] wall = emptySpaces.get(wallIdx);
            newMap[wall[0]][wall[1]] = 1;
        }

        return newMap;
    }
    static void backtracking(int start, List<int[]> emptySpaces, List<Integer> cur){
        if (cur.size() == WALL_CNT) {
            wallList.add(new ArrayList<>(cur));
            return;
        }
        for (int i = start; i < emptySpaces.size(); i++) {
            if (!cur.contains(i)) {
                cur.add(i);
                backtracking(i + 1, emptySpaces, cur);
                cur.remove(cur.size() - 1);
            }
        }
    }
}