문제

연구소 - 골드 4

---

문제 이해

1. 벽을 3개 세운다.
2. 바이러스가 더이상 퍼지지 않을때까지 퍼지게 한다.
3. 안전한 영역의 크기를 최대값으로 계속해서 갱신한다.

1. 해결책 -> 벽을 3개 세우기 위해서는 DFS(depth = 3), Back Tracking을 사용해서 벽을 세운다.
2. 해결책 -> BFS를 이용해서 바이러스를 계속해서 퍼지게 한다.
3. 해결책 -> Math.max() 메서드 이용

---

코드

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

public class BaekJoon_14502 {
  static int[][] board;
  static int N;
  static int M;
  static int count;
  static int[] moveR = { -1, 1, 0, 0 };
  static int[] moveC = { 0, 0, -1, 1 };
  static Queue<Location> queue;

  public static class Location {
    int r;
    int c;

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

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    board = new int[N][M];
    queue = new LinkedList<>();

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < M; j++) {
        board[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    makeWall(0);
    System.out.println(count);
  }

  public static void makeWall(int depth) {
    if (depth == 3) {
      bfs();
      return;
    }
    
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        if (board[i][j] == 0) {
          board[i][j] = 1;
          makeWall(depth + 1);
          board[i][j] = 0;
        }
      }
    }
  }

  public static void bfs() {
    Queue<Location> Q = new LinkedList<>(queue);
    int[][] matrix = new int[N][M];

    for (int i = 0; i < N; i++) {
      matrix[i] = board[i].clone();
      for (int j = 0; j < M; j++) {
        if (board[i][j] == 2)
          Q.add(new Location(i, j));
      }
    }

    while (!Q.isEmpty()) {
      Location current = Q.poll();

      for (int i = 0; i < 4; i++) {
        int currentR = current.r + moveR[i];
        int currentC = current.c + moveC[i];

        if (0 <= currentR && currentR < N && 0 <= currentC && currentC < M) {
          if (matrix[currentR][currentC] == 0) {
            matrix[currentR][currentC] = 2;
            Q.add(new Location(currentR, currentC));
          }
        }
      }
    }
    compareCount(matrix);
  }

  public static void compareCount(int[][] matrix) {
    int c = 0;
    for (int i = 0; i < N; i++)
      for (int j = 0; j < M; j++)
        if (matrix[i][j] == 0)
          c++;
    count = Math.max(c, count);
  }
}

---

코드 설명

• DFS로 벽만들기
  3개의 벽을 만들어야 하기 때문에 depth를 0부터 시작해서 3으로 종료될때 까지 재귀적으로 벽을 세운다. 종료가 되었을때 BFS 알고리즘을 이용하여 바이러스를 퍼뜨리게 된다.
  순차적으로 탐색하면서 벽을 세울 수 있으면 해당 영역을 벽으로 세우고 재귀 호출을 수행한다. 그리고 나서 벽을 세웠던 부분을 다시 초기화하며 depth가 3이 될 때까지 반복한다.

• BFS로 바이러스 퍼뜨리기 및 안전한 영역 최대값 찾기
  바이러스가 있는 영역을 queue에 넣고 탐색을 수행한다. 바이러스는 상,하,좌,우로만 퍼질 수 있고 벽을 넘지 못하므로 해당 조건에 맞는 영역들을 queue에 넣고 바이러스르 퍼뜨린다.
  BFS 탐색이 끝난다면 안전 영역의 개수를 구해 최대값으로 갱신한다.

---