[14502] 연구소

🔗 문제 링크

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

🔍 문제 설명

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

연구소는 크기가 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이다.

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

⚠️ 제한사항

• $(3 ≤ N, M ≤ 8)$

• 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다.

• 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

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

---

🗝 풀이 (언어 : Java)

삼성 SW 역량 테스트 문제 중 하나이다. 구현하기 상당히 복잡해서 어려웠다. 공부하고 다시 풀어 보았다. 작성한 풀이는 DFS와 BFS를 모두 사용한다. 3개의 벽을 설치할 위치별 경우의 수는 DFS, 벽 설치 후에 바이러스를 전파시키는 것은 BFS를 사용한다. 처음에 반복문을 추가로 한번 실행해서 모든 공백의 위치와, 숙주 바이러스의 위치를 저장했다. 초기 바이러스의 위치와 빈공간의 위치는 불변하기 때문이다. (빈공간은 전염되어도 수정하지 않고 방문 배열을 true로 바꾸어 체크했다.) 이것을 이용해 답도 수학적으로 계산해서 정답을 구하기 위해 반복문을 계속 돌지 않도록 했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    private List<int[]> blanks = new ArrayList<>();
    private List<int[]> viruses = new ArrayList<>();
    private int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int maximum = 0;
    private boolean[][] visited;

    private void bfs(int n, int m, int[][] matrix) {
        Queue<int[]> queue = new LinkedList<>();
        // 바이러스 위치에서만 시작해서 전파 탐색
        for (int[] virus : viruses) {
            queue.add(virus);
            visited[virus[0]][virus[1]] = true;
        }
        // bfs
        int virusCount = 0; // 전파된 바이러스 개수만 세기(초기 바이러스는 x)
        while (!queue.isEmpty()) {
            int[] virus = queue.poll();
            int x = virus[0], y = virus[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dirs[i][0], ny = y + dirs[i][1];
                // 범위를 넘어서거나, 이미 방문했거나, 빈공간이 아니면 종료
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny] || matrix[nx][ny] != 0)
                    continue;
                // 방문 처리하고 큐에 넣어 다음 전파 위치 찾기, 원본은 수정하지 않고 visited로 판별
                visited[nx][ny] = true;
                virusCount++;
                queue.add(new int[]{nx, ny});
            }
        }
        // 안전구역 = 모든 공백수 - 벽세운 수 - 전파된 바이러스 수
        int count = blanks.size() - (3 + virusCount);
        maximum = Math.max(maximum, count);
    }

    // 모든 벽 설치 가능한 지점별 모든 경우의 수, 설치 완료 후에 빈 공간 개수 세는 함수 호출
    private void findBlockCases(int idx, int selected, int length, int[][] matrix, int n, int m) {
        // 벽 3개 설치 경우별 완료후, 바이러스 전파시키고 결과로 최대값 갱신
        if (selected == 3) {
            visited = new boolean[n][m]; // 방문 여부 배열 매번 초기화, BFS에서 전염된 위치들 다시 false로
            bfs(n, m, matrix);
            return;
        }
        // 설치 가능한 최대 벽의 개수 초과 불가능
        if (idx >= length)
            return;
        int[] blank = blanks.get(idx);
        // 해당 위치의 빈칸에 벽설치하고 다음 순서의 벽으로
        matrix[blank[0]][blank[1]] = 1;
        findBlockCases(idx + 1, selected + 1, length, matrix, n, m);
        // 해당 위치의 빈칸에 벽설치 안하고 다음 순서의 벽으로
        matrix[blank[0]][blank[1]] = 0;
        findBlockCases(idx + 1, selected, length, matrix, n, m);
    }

    // 연구소의 모든 빈 공간, 바이러스의 좌표 찾기
    private void findBlankAndVirus(int n, int m, int[][] matrix) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 0)
                    blanks.add(new int[]{i, j});
                else if (matrix[i][j] == 2)
                    viruses.add(new int[]{i, j});
            }
        }
    }

    // 정답 찾기
    private void findSafeAreas(int n, int m, int[][] matrix) {
        // 모든 빈공간, 바이러스 위치를 찾아서 보관
        findBlankAndVirus(n, m, matrix);
        // 빈공간에 벽 3개를 각각 놓거나, 안놓거나 모든 경우의 수
        findBlockCases(0, 0, blanks.size(), matrix, n, m);
        System.out.print(maximum); // 정답 출력
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < m; j++)
                matrix[i][j] = Integer.parseInt(st2.nextToken());
        }
        br.close();
        new Main().findSafeAreas(n, m, matrix);
    }
}