백준 - 14502번 - 연구소 (java)

1. 문제

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

2606번: 바이러스

문제 설명

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

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

출력

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

입출력 예

---

2. 어떻게 풀까?

• 벽을 먼저 3개 세운다.
• 바이러스(2)를 중심으로 바이러스를 퍼뜨린다.
• 0의 개수를 카운팅 한다.
• 벽 세우는 것을 어떻게 할까?
  • DFS를 이용해서 벽을 세운다

  • 

• 바이러스는 어떻게 퍼뜨릴까?
  • BFS나 BFS를 이용한다.
• 벽이 3개 세워지는 모든 경우에서 0개수의 최대값을 찾아낸다.
• 그리고 0개수를 출력!

---

3. 코드

백준문제는 입,출력을 사용자가 직접 해야해서 테스트코드를 따로 만들지 않았다.

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

class Main {

  private static final BufferedReader READER = new BufferedReader(new InputStreamReader(System.in));
  private static final BufferedWriter WRITER = new BufferedWriter(new OutputStreamWriter(System.out));
  private static StringTokenizer tokenizer;
  
  private static int maxSafeZone = Integer.MIN_VALUE;
  private static int row;
  private static int col;
  private static int[] yPoint = {1, -1, 0, 0};
  private static int[] xPoint = {0, 0, 1, -1};

  public static void main(String[] args) throws IOException {
    tokenizer = new StringTokenizer(READER.readLine());
    row = Integer.parseInt(tokenizer.nextToken());
    col = Integer.parseInt(tokenizer.nextToken());

    int[][] map = buildMap();
    installWall(map, 0);

    WRITER.write(maxSafeZone + "");
    WRITER.flush();
    WRITER.close();
    READER.close();
  }
  
  private static int[][] buildMap() throws IOException {
  	int[][] map = new int[row][col];
    for (int i = 0; i < row; i++) {
      tokenizer = new StringTokenizer(READER.readLine());
      for (int j = 0; j < col; j++) {
        map[i][j] = Integer.parseInt(tokenizer.nextToken());
      }
    }
    return map;
  }

  private static void installWall(int[][] map, int wallCount) {
    if (wallCount == 3) {
      int[][] virusMap = spreadVirus(map);
      int safeZone = countSafeZone(virusMap);
      maxSafeZone = Math.max(safeZone, maxSafeZone);
      return;
    }

    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        if (map[i][j] == 0) {
          map[i][j] = 1;
          installWall(map, wallCount + 1);
          map[i][j] = 0;
        }
      }
    }
  }

  private static int countSafeZone(int[][] map) {
    int count = 0;
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        if (map[i][j] == 0) {
          count++;
        }
      }
    }
    return count;
  }

  private static int[][] spreadVirus(int[][] map) {
    int[][] copyMap = new int[row][col];
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        copyMap[i][j] = map[i][j];
      }
    }

    boolean[][] visit = new boolean[row][col];

    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        if (copyMap[i][j] == 2 && !visit[i][j]) {
          bfs(copyMap, visit, i, j);
        }
      }
    }
    return copyMap;
  }

  private static void bfs(int[][] map, boolean[][] visit, int startY, int startX) {
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{startY, startX});
    visit[startY][startX] = true;

    while (!queue.isEmpty()) {
      int[] current = queue.poll();

      for (int i = 0; i < 4; i++) {
        int y = current[0] + yPoint[i];
        int x = current[1] + xPoint[i];

        if (y < 0 || y >= row) {
          continue;
        }
        if (x < 0 || x >= col) {
          continue;
        }
        if (map[y][x] == 0 && !visit[y][x]) {
          visit[y][x] = true;
          map[y][x] = 2;
          queue.add(new int[]{y, x});
        }
      }
    }
  }

}

• buildMap() : 입력으로 받은 정보로 연구소 지도를 만든다.
• installWall(int[][] map, int wallCount) : DFS를 이용하여 0을 1로 바꿔 벽을 세운다. 벽이 3개이면 바이러스를 퍼뜨리고 안전한 장소(0)을 카운팅한다.
• countSafeZone(int[][] map) : 0 개수를 카운팅한다.
• spreadVirus(int[][] map) : 연구소 지도를 돌며 2인 지점을 찾아내고 2에서 bfs()를 통해 바이러스를 퍼뜨린다.
• bfs(int[][] map, boolean[][] visit, int startY, int startX) : 2인 지점을 시작으로 바이러스를 퍼뜨린다 ( 0 -> 2)

---

4. 느낀 점

• 벽을 설치하는 과정이 Brute-Force라서 시간초과 되지 않을까? 라는 생각에 다른 방법을 생각하다가 더 생각이 안나서 그냥 Brute-Force 방식을 사용했다.
• 그 외에는 딱히 어려운 것 없는 문제